Constructing Orthogonal de Bruijn Sequences
Identifieur interne : 000108 ( Istex/Curation ); précédent : 000107; suivant : 000109Constructing Orthogonal de Bruijn Sequences
Auteurs : Yaw-Ling Lin [Taïwan] ; Charles Ward [États-Unis] ; Bharat Jain [États-Unis] ; Steven Skiena [États-Unis]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: 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 $\lfloor \sigma/2 \rfloor$ 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.
Url:
DOI: 10.1007/978-3-642-22300-6_50
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000108
Links to Exploration step
ISTEX:A124422C0C3BFEC162C72EC2D2316653ED2B29F2Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Constructing Orthogonal de Bruijn Sequences</title>
<author><name sortKey="Lin, Yaw Ling" sort="Lin, Yaw Ling" uniqKey="Lin Y" first="Yaw-Ling" last="Lin">Yaw-Ling Lin</name>
<affiliation wicri:level="1"><mods:affiliation>Dept. of Comp. Sci. and Info. Eng., Providence University, Taiwan</mods:affiliation>
<country xml:lang="fr">Taïwan</country>
<wicri:regionArea>Dept. of Comp. Sci. and Info. Eng., Providence University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: yllin@pu.edu.tw</mods:affiliation>
<country wicri:rule="url">Taïwan</country>
</affiliation>
</author>
<author><name sortKey="Ward, Charles" sort="Ward, Charles" uniqKey="Ward C" first="Charles" last="Ward">Charles Ward</name>
<affiliation wicri:level="1"><mods:affiliation>Dept. of Comp. Sci., Stony Brook University, USA</mods:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Dept. of Comp. Sci., Stony Brook University</wicri:regionArea>
</affiliation>
<affiliation><mods:affiliation>E-mail: charlesbward@gmail.com</mods:affiliation>
<wicri:noCountry code="no comma">E-mail: charlesbward@gmail.com</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Jain, Bharat" sort="Jain, Bharat" uniqKey="Jain B" first="Bharat" last="Jain">Bharat Jain</name>
<affiliation wicri:level="1"><mods:affiliation>Dept. of Comp. Sci., Stony Brook University, USA</mods:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Dept. of Comp. Sci., Stony Brook University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: bkjain@cs.sunysb.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Skiena, Steven" sort="Skiena, Steven" uniqKey="Skiena S" first="Steven" last="Skiena">Steven Skiena</name>
<affiliation wicri:level="1"><mods:affiliation>Dept. of Comp. Sci., Stony Brook University, USA</mods:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Dept. of Comp. Sci., Stony Brook University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: skiena@cs.sunysb.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:A124422C0C3BFEC162C72EC2D2316653ED2B29F2</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-22300-6_50</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-XTDFGC6N-5/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000108</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000108</idno>
<idno type="wicri:Area/Istex/Curation">000108</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Constructing Orthogonal de Bruijn Sequences</title>
<author><name sortKey="Lin, Yaw Ling" sort="Lin, Yaw Ling" uniqKey="Lin Y" first="Yaw-Ling" last="Lin">Yaw-Ling Lin</name>
<affiliation wicri:level="1"><mods:affiliation>Dept. of Comp. Sci. and Info. Eng., Providence University, Taiwan</mods:affiliation>
<country xml:lang="fr">Taïwan</country>
<wicri:regionArea>Dept. of Comp. Sci. and Info. Eng., Providence University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: yllin@pu.edu.tw</mods:affiliation>
<country wicri:rule="url">Taïwan</country>
</affiliation>
</author>
<author><name sortKey="Ward, Charles" sort="Ward, Charles" uniqKey="Ward C" first="Charles" last="Ward">Charles Ward</name>
<affiliation wicri:level="1"><mods:affiliation>Dept. of Comp. Sci., Stony Brook University, USA</mods:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Dept. of Comp. Sci., Stony Brook University</wicri:regionArea>
</affiliation>
<affiliation><mods:affiliation>E-mail: charlesbward@gmail.com</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Jain, Bharat" sort="Jain, Bharat" uniqKey="Jain B" first="Bharat" last="Jain">Bharat Jain</name>
<affiliation wicri:level="1"><mods:affiliation>Dept. of Comp. Sci., Stony Brook University, USA</mods:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Dept. of Comp. Sci., Stony Brook University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: bkjain@cs.sunysb.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Skiena, Steven" sort="Skiena, Steven" uniqKey="Skiena S" first="Steven" last="Skiena">Steven Skiena</name>
<affiliation wicri:level="1"><mods:affiliation>Dept. of Comp. Sci., Stony Brook University, USA</mods:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Dept. of Comp. Sci., Stony Brook University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: skiena@cs.sunysb.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: 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 $\lfloor \sigma/2 \rfloor$ 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.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000108 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 000108 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:A124422C0C3BFEC162C72EC2D2316653ED2B29F2 |texte= Constructing Orthogonal de Bruijn Sequences }}
This area was generated with Dilib version V0.6.33. |