TY - GEN
T1 - Constructing orthogonal de Bruijn sequences
AU - Lin, Yaw Ling
AU - Ward, Charles
AU - Jain, Bharat
AU - Skiena, Steven
PY - 2011
Y1 - 2011
N2 - A (σ,k)-de Bruijn sequence is a minimum length string on an alphabet set of size σ which contains all σk k-mers exactly once. Motivated by an application in synthetic biology, we say a given collection of de Bruijn sequences are orthogonal if no two of them contain the same (k + 1)-mer; that is, the length of their longest common substring is k. In this paper, we show how to construct large collections of orthogonal de Bruijn sequences. In particular, we prove that there are at least ⌊σ/ 2⌋ mutually-orthogonal order-k de Bruijn sequences on alphabets of size σ for all k. Based on this approach, we present a heuristic which proves capable of efficiently constructing optimal collections of mutually-orthogonal sequences for small values of σ and k, which supports our conjecture that σ - 1 mutually-orthogonal de Bruijn sequences exist for all σ and k.
AB - A (σ,k)-de Bruijn sequence is a minimum length string on an alphabet set of size σ which contains all σk k-mers exactly once. Motivated by an application in synthetic biology, we say a given collection of de Bruijn sequences are orthogonal if no two of them contain the same (k + 1)-mer; that is, the length of their longest common substring is k. In this paper, we show how to construct large collections of orthogonal de Bruijn sequences. In particular, we prove that there are at least ⌊σ/ 2⌋ mutually-orthogonal order-k de Bruijn sequences on alphabets of size σ for all k. Based on this approach, we present a heuristic which proves capable of efficiently constructing optimal collections of mutually-orthogonal sequences for small values of σ and k, which supports our conjecture that σ - 1 mutually-orthogonal de Bruijn sequences exist for all σ and k.
KW - de Bruijn graphs
KW - de Bruijn sequences
KW - DNA synthesis
KW - Eulerian cycles
KW - orthogonal sequences
UR - https://www.scopus.com/pages/publications/80052130066
U2 - 10.1007/978-3-642-22300-6_50
DO - 10.1007/978-3-642-22300-6_50
M3 - Conference contribution
AN - SCOPUS:80052130066
SN - 9783642222993
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 595
EP - 606
BT - Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings
T2 - 12th International Symposium on Algorithms and Data Structures, WADS 2011
Y2 - 15 August 2011 through 17 August 2011
ER -