Efficient Design of Compact Unstructured RNA Libraries Covering Allk-mers

摘要

>Current microarray technologies to determine RNA structure or measure protein–RNA interactions rely on single-stranded, unstructured RNA probes on a chip covering together all k-mers. Since space on the array is limited, the problem is to efficiently design a compact library of unstructured ℓ-long RNA probes, where each k-mer is covered at least p times. Ray et al. designed such a library for specific values of k, ℓ, and p using ad-hoc rules. To our knowledge, there is no general method to date to solve this problem. Here, we address the problem of finding a minimum-size covering of all k-mers by ℓ-long sequences with the desired properties for any value of k, ℓ, and p. As we prove that the problem is NP-hard, we give two solutions: the first is a greedy algorithm with a logarithmic approximation ratio; the second, a heuristic greedy approach based on random walks in de Bruijn graphs. The heuristic algorithm works well in practice and produces a library of unstructured RNA probes that is only ∼1.1-times greater in size compared to the theoretical lower bound. Wepresent results for typical values of k and probe lengthsℓ and show that our algorithm generates a library thatis significantly smaller than the library of Ray et al.; moreover, we show thatour algorithm outperforms naive methods. Our approach can be generalized andextended to generate RNA or DNA oligo libraries with other desired properties. Thesoftware is freely available online.