Constructing Orthogonal de Bruijn Sequences
Identifieur interne : 002573 ( Main/Exploration ); précédent : 002572; suivant : 002574Constructing 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
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000108
- to stream Istex, to step Curation: 000108
- to stream Istex, to step Checkpoint: 000502
- to stream Main, to step Merge: 002598
- to stream Main, to step Curation: 002573
Le 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></author><author><name sortKey="Ward, Charles" sort="Ward, Charles" uniqKey="Ward C" first="Charles" last="Ward">Charles Ward</name></author><author><name sortKey="Jain, Bharat" sort="Jain, Bharat" uniqKey="Jain B" first="Bharat" last="Jain">Bharat Jain</name></author><author><name sortKey="Skiena, Steven" sort="Skiena, Steven" uniqKey="Skiena S" first="Steven" last="Skiena">Steven Skiena</name></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><idno type="wicri:Area/Istex/Checkpoint">000502</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000502</idno><idno type="wicri:doubleKey">0302-9743:2011:Lin Y:constructing:orthogonal:de</idno><idno type="wicri:Area/Main/Merge">002598</idno><idno type="wicri:Area/Main/Curation">002573</idno><idno type="wicri:Area/Main/Exploration">002573</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"><country xml:lang="fr">Taïwan</country><wicri:regionArea>Dept. of Comp. Sci. and Info. Eng., Providence University</wicri:regionArea><wicri:noRegion>Providence University</wicri:noRegion></affiliation><affiliation wicri:level="1"><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"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Dept. of Comp. Sci., Stony Brook University</wicri:regionArea><wicri:noRegion>Stony Brook University</wicri:noRegion></affiliation><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"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Dept. of Comp. Sci., Stony Brook University</wicri:regionArea><wicri:noRegion>Stony Brook University</wicri:noRegion></affiliation><affiliation wicri:level="1"><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"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Dept. of Comp. Sci., Stony Brook University</wicri:regionArea><wicri:noRegion>Stony Brook University</wicri:noRegion></affiliation><affiliation wicri:level="1"><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><affiliations><list><country><li>Taïwan</li><li>États-Unis</li></country></list><tree><country name="Taïwan"><noRegion><name sortKey="Lin, Yaw Ling" sort="Lin, Yaw Ling" uniqKey="Lin Y" first="Yaw-Ling" last="Lin">Yaw-Ling Lin</name></noRegion><name sortKey="Lin, Yaw Ling" sort="Lin, Yaw Ling" uniqKey="Lin Y" first="Yaw-Ling" last="Lin">Yaw-Ling Lin</name></country><country name="États-Unis"><noRegion><name sortKey="Ward, Charles" sort="Ward, Charles" uniqKey="Ward C" first="Charles" last="Ward">Charles Ward</name></noRegion><name sortKey="Jain, Bharat" sort="Jain, Bharat" uniqKey="Jain B" first="Bharat" last="Jain">Bharat Jain</name><name sortKey="Jain, Bharat" sort="Jain, Bharat" uniqKey="Jain B" first="Bharat" last="Jain">Bharat Jain</name><name sortKey="Skiena, Steven" sort="Skiena, Steven" uniqKey="Skiena S" first="Steven" last="Skiena">Steven Skiena</name><name sortKey="Skiena, Steven" sort="Skiena, Steven" uniqKey="Skiena S" first="Steven" last="Skiena">Steven Skiena</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002573 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002573 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:A124422C0C3BFEC162C72EC2D2316653ED2B29F2
|texte= Constructing Orthogonal de Bruijn Sequences
}}
| This area was generated with Dilib version V0.6.33. |  |