Joker de Bruijn: Covering k-Mers Using Joker Characters

Journal of computational biology: A journal of computational molecular cell biology

Yun WilliamYu^3²  YaronOrenstein^1,2³  BonnieBerger^4,2,3⁴ 

[1] Address correspondence to: Prof. Bonnie Berger, Department of Mathematics, Massachusetts Institute of Technology, 77 Mass Avenue, 2-373, Cambridge, MA 02139^4;Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts^2;Department of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel^1;Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts^3

关键词: de Bruijn sequence;    microarray library design;    peptide arrays;    protein binding;    protein binding microarrays;   

DOI  :  10.1089/cmb.2018.0032

学科分类：生物科学（综合）

来源: Mary Ann Liebert, Inc. Publishers

【 摘 要 】

Sequence libraries that cover all k-mers enable universal and unbiased measurements of nucleotide and peptide binding. The shortest sequence to cover all k-mers is a de Bruijn sequence of length . Researchers would like to increase k to measure interactions at greater detail, but face a challenging problem: the number of k-mers grows exponentially in k, while the space on the experimental device is limited. In this study, we introduce a novel advance to shrink k-mer library sizes by using joker characters, which represent all characters in the alphabet. Theoretically, the use of joker characters can reduce the library size tremendously, but it should be limited as the introduced degeneracy lowers the statistical robustness of measurements. In this work, we consider the problem of generating a minimum-length sequence that covers a given set of k-mers using joker characters. The number and positions of the joker characters are provided as input. We first prove that the problem is NP-hard. We then present the first solution to the problem, which is based on two algorithmic innovations: (1) a greedy heuristic and (2) an integer linear programming (ILP) formulation. We first run the heuristic to find a good feasible solution, and then run an ILP solver to improve it. We ran our algorithm on DNA and amino acid alphabets to cover all k-mers for different values of k and k-mer multiplicity. Results demonstrate that it produces sequences that are very close to the theoretical lower bound.

【 授权许可】

Unknown