A fast algorithm for the construction of universal footprinting templates in DNA.
Identifieur interne : 002294 ( PubMed/Corpus ); précédent : 002293; suivant : 002295A fast algorithm for the construction of universal footprinting templates in DNA.
Auteurs : James W. Anderson ; Keith R. Fox ; Graham A. NibloSource :
- Journal of mathematical biology [ 0303-6812 ] ; 2006.
English descriptors
- KwdEn :
- MESH :
- chemical , chemistry : DNA, Oligodeoxyribonucleotides.
- genetics : Base Pairing, DNA, Oligodeoxyribonucleotides.
- methods : DNA Footprinting.
- Algorithms, Sequence Analysis, DNA.
Abstract
We introduce and give a complete description of a new graph to be used for DNA sequencing questions. This graph has the advantage over the classical de Bruijn graph that it fully accounts for the double stranded nature of DNA, rather than dealing with single strands. Technically, our graph may be thought of as the quotient of the de Bruijn graph under the natural involution of sending a DNA strand to its complementary strand. However, this involution has fixed points, and this complicates the structure of the quotient graph which we have therefore modified herein. As an application and motivating example, we give an efficient algorithm for constructing universal footprinting templates for n-mers. This problem may be formulated as the task of finding a shortest possible segment of DNA which contains every possible sequence of base pairs of some fixed length n. Previous work by Kwan et al has attacked this problem from a numerical point of view and generated minimal length universal footprinting templates for n = 2, 3, 5, 7, together with unsubstantiated candidates for the case n = 4. We show that their candidates for n = 4 are indeed minimal length universal footprinting templates.
DOI: 10.1007/s00285-005-0357-z
PubMed: 16328479
Links to Exploration step
pubmed:16328479Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">A fast algorithm for the construction of universal footprinting templates in DNA.</title><author><name sortKey="Anderson, James W" sort="Anderson, James W" uniqKey="Anderson J" first="James W" last="Anderson">James W. Anderson</name><affiliation><nlm:affiliation>School of Mathematics, University of Southampton, Southampton, SO17 1BJ, United Kingdom. j.w.anderson@soton.ac.uk</nlm:affiliation></affiliation></author><author><name sortKey="Fox, Keith R" sort="Fox, Keith R" uniqKey="Fox K" first="Keith R" last="Fox">Keith R. Fox</name></author><author><name sortKey="Niblo, Graham A" sort="Niblo, Graham A" uniqKey="Niblo G" first="Graham A" last="Niblo">Graham A. Niblo</name></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2006">2006</date><idno type="RBID">pubmed:16328479</idno><idno type="pmid">16328479</idno><idno type="doi">10.1007/s00285-005-0357-z</idno><idno type="wicri:Area/PubMed/Corpus">002294</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">002294</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">A fast algorithm for the construction of universal footprinting templates in DNA.</title><author><name sortKey="Anderson, James W" sort="Anderson, James W" uniqKey="Anderson J" first="James W" last="Anderson">James W. Anderson</name><affiliation><nlm:affiliation>School of Mathematics, University of Southampton, Southampton, SO17 1BJ, United Kingdom. j.w.anderson@soton.ac.uk</nlm:affiliation></affiliation></author><author><name sortKey="Fox, Keith R" sort="Fox, Keith R" uniqKey="Fox K" first="Keith R" last="Fox">Keith R. Fox</name></author><author><name sortKey="Niblo, Graham A" sort="Niblo, Graham A" uniqKey="Niblo G" first="Graham A" last="Niblo">Graham A. Niblo</name></author></analytic><series><title level="j">Journal of mathematical biology</title><idno type="ISSN">0303-6812</idno><imprint><date when="2006" type="published">2006</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Base Pairing (genetics)</term><term>DNA (chemistry)</term><term>DNA (genetics)</term><term>DNA Footprinting (methods)</term><term>Oligodeoxyribonucleotides (chemistry)</term><term>Oligodeoxyribonucleotides (genetics)</term><term>Sequence Analysis, DNA</term></keywords><keywords scheme="MESH" type="chemical" qualifier="chemistry" xml:lang="en"><term>DNA</term><term>Oligodeoxyribonucleotides</term></keywords><keywords scheme="MESH" qualifier="genetics" xml:lang="en"><term>Base Pairing</term><term>DNA</term><term>Oligodeoxyribonucleotides</term></keywords><keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>DNA Footprinting</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Algorithms</term><term>Sequence Analysis, DNA</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We introduce and give a complete description of a new graph to be used for DNA sequencing questions. This graph has the advantage over the classical de Bruijn graph that it fully accounts for the double stranded nature of DNA, rather than dealing with single strands. Technically, our graph may be thought of as the quotient of the de Bruijn graph under the natural involution of sending a DNA strand to its complementary strand. However, this involution has fixed points, and this complicates the structure of the quotient graph which we have therefore modified herein. As an application and motivating example, we give an efficient algorithm for constructing universal footprinting templates for n-mers. This problem may be formulated as the task of finding a shortest possible segment of DNA which contains every possible sequence of base pairs of some fixed length n. Previous work by Kwan et al has attacked this problem from a numerical point of view and generated minimal length universal footprinting templates for n = 2, 3, 5, 7, together with unsubstantiated candidates for the case n = 4. We show that their candidates for n = 4 are indeed minimal length universal footprinting templates.</div></front></TEI><pubmed><MedlineCitation Status="MEDLINE" Owner="NLM"><PMID Version="1">16328479</PMID><DateCompleted><Year>2006</Year><Month>09</Month><Day>11</Day></DateCompleted><DateRevised><Year>2018</Year><Month>11</Month><Day>13</Day></DateRevised><Article PubModel="Print-Electronic"><Journal><ISSN IssnType="Print">0303-6812</ISSN><JournalIssue CitedMedium="Print"><Volume>52</Volume><Issue>3</Issue><PubDate><Year>2006</Year><Month>Mar</Month></PubDate></JournalIssue><Title>Journal of mathematical biology</Title><ISOAbbreviation>J Math Biol</ISOAbbreviation></Journal><ArticleTitle>A fast algorithm for the construction of universal footprinting templates in DNA.</ArticleTitle><Pagination><MedlinePgn>307-42</MedlinePgn></Pagination><Abstract><AbstractText>We introduce and give a complete description of a new graph to be used for DNA sequencing questions. This graph has the advantage over the classical de Bruijn graph that it fully accounts for the double stranded nature of DNA, rather than dealing with single strands. Technically, our graph may be thought of as the quotient of the de Bruijn graph under the natural involution of sending a DNA strand to its complementary strand. However, this involution has fixed points, and this complicates the structure of the quotient graph which we have therefore modified herein. As an application and motivating example, we give an efficient algorithm for constructing universal footprinting templates for n-mers. This problem may be formulated as the task of finding a shortest possible segment of DNA which contains every possible sequence of base pairs of some fixed length n. Previous work by Kwan et al has attacked this problem from a numerical point of view and generated minimal length universal footprinting templates for n = 2, 3, 5, 7, together with unsubstantiated candidates for the case n = 4. We show that their candidates for n = 4 are indeed minimal length universal footprinting templates.</AbstractText></Abstract><AuthorList CompleteYN="Y"><Author ValidYN="Y"><LastName>Anderson</LastName><ForeName>James W</ForeName><Initials>JW</Initials><AffiliationInfo><Affiliation>School of Mathematics, University of Southampton, Southampton, SO17 1BJ, United Kingdom. j.w.anderson@soton.ac.uk</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Fox</LastName><ForeName>Keith R</ForeName><Initials>KR</Initials></Author><Author ValidYN="Y"><LastName>Niblo</LastName><ForeName>Graham A</ForeName><Initials>GA</Initials></Author></AuthorList><Language>eng</Language><PublicationTypeList><PublicationType UI="D016428">Journal Article</PublicationType></PublicationTypeList><ArticleDate DateType="Electronic"><Year>2005</Year><Month>11</Month><Day>21</Day></ArticleDate></Article><MedlineJournalInfo><Country>Germany</Country><MedlineTA>J Math Biol</MedlineTA><NlmUniqueID>7502105</NlmUniqueID><ISSNLinking>0303-6812</ISSNLinking></MedlineJournalInfo><ChemicalList><Chemical><RegistryNumber>0</RegistryNumber><NameOfSubstance UI="D009838">Oligodeoxyribonucleotides</NameOfSubstance></Chemical><Chemical><RegistryNumber>9007-49-2</RegistryNumber><NameOfSubstance UI="D004247">DNA</NameOfSubstance></Chemical></ChemicalList><CitationSubset>IM</CitationSubset><MeshHeadingList><MeshHeading><DescriptorName UI="D000465" MajorTopicYN="Y">Algorithms</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D020029" MajorTopicYN="N">Base Pairing</DescriptorName><QualifierName UI="Q000235" MajorTopicYN="N">genetics</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D004247" MajorTopicYN="N">DNA</DescriptorName><QualifierName UI="Q000737" MajorTopicYN="N">chemistry</QualifierName><QualifierName UI="Q000235" MajorTopicYN="N">genetics</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D018983" MajorTopicYN="N">DNA Footprinting</DescriptorName><QualifierName UI="Q000379" MajorTopicYN="Y">methods</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D009838" MajorTopicYN="N">Oligodeoxyribonucleotides</DescriptorName><QualifierName UI="Q000737" MajorTopicYN="N">chemistry</QualifierName><QualifierName UI="Q000235" MajorTopicYN="N">genetics</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D017422" MajorTopicYN="N">Sequence Analysis, DNA</DescriptorName></MeshHeading></MeshHeadingList></MedlineCitation><PubmedData><History><PubMedPubDate PubStatus="received"><Year>2005</Year><Month>01</Month><Day>17</Day></PubMedPubDate><PubMedPubDate PubStatus="revised"><Year>2005</Year><Month>07</Month><Day>17</Day></PubMedPubDate><PubMedPubDate PubStatus="pubmed"><Year>2005</Year><Month>12</Month><Day>6</Day><Hour>9</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="medline"><Year>2006</Year><Month>9</Month><Day>12</Day><Hour>9</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="entrez"><Year>2005</Year><Month>12</Month><Day>6</Day><Hour>9</Hour><Minute>0</Minute></PubMedPubDate></History><PublicationStatus>ppublish</PublicationStatus><ArticleIdList><ArticleId IdType="pubmed">16328479</ArticleId><ArticleId IdType="doi">10.1007/s00285-005-0357-z</ArticleId></ArticleIdList><ReferenceList><Reference><Citation>Anal Biochem. 2001 Jun 15;293(2):246-50</Citation><ArticleIdList><ArticleId IdType="pubmed">11399039</ArticleId></ArticleIdList></Reference><Reference><Citation>Proc Natl Acad Sci U S A. 2001 Aug 14;98(17):9748-53</Citation><ArticleIdList><ArticleId IdType="pubmed">11504945</ArticleId></ArticleIdList></Reference><Reference><Citation>Nucleic Acids Res. 1978 Sep;5(9):3157-70</Citation><ArticleIdList><ArticleId IdType="pubmed">212715</ArticleId></ArticleIdList></Reference><Reference><Citation>Methods Enzymol. 2001;340:412-30</Citation><ArticleIdList><ArticleId IdType="pubmed">11529207</ArticleId></ArticleIdList></Reference><Reference><Citation>Nucleic Acids Res. 2003 Oct 15;31(20):e124</Citation><ArticleIdList><ArticleId IdType="pubmed">14530457</ArticleId></ArticleIdList></Reference><Reference><Citation>Mol Biotechnol. 1997 Aug;8(1):35-52</Citation><ArticleIdList><ArticleId IdType="pubmed">9327396</ArticleId></ArticleIdList></Reference></ReferenceList></PubmedData></pubmed></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/PubMed/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002294 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PubMed/Corpus/biblio.hfd -nk 002294 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= PubMed
|étape= Corpus
|type= RBID
|clé= pubmed:16328479
|texte= A fast algorithm for the construction of universal footprinting templates in DNA.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/PubMed/Corpus/RBID.i -Sk "pubmed:16328479" \
| HfdSelect -Kh $EXPLOR_AREA/Data/PubMed/Corpus/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |