Handling long targets and errors in sequencing by hybridization.
Identifieur interne : 000210 ( Ncbi/Merge ); précédent : 000209; suivant : 000211Handling long targets and errors in sequencing by hybridization.
Auteurs : Eran Halperin [États-Unis] ; Shay Halperin ; Tzvika Hartman ; Ron ShamirSource :
- Journal of computational biology : a journal of computational molecular cell biology [ 1066-5277 ] ; 2003.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
Abstract
Sequencing by hybridization (SBH) is a DNA sequencing technique, in which the sequence is reconstructed using its k-mer content. This content, which is called the spectrum of the sequence, is obtained by hybridization to a universal DNA array. Standard universal arrays contain all k-mers for some fixed k, typically 8 to 10. Currently, in spite of its promise and elegance, SBH is not competitive with standard gel-based sequencing methods. This is due to two main reasons: lack of tools to handle realistic levels of hybridization errors and an inherent limitation on the length of uniquely reconstructible sequence by standard universal arrays. In this paper, we deal with both problems. We introduce a simple polynomial reconstruction algorithm which can be applied to spectra from standard arrays and has provable performance in the presence of both false negative and false positive errors. We also propose a novel design of chips containing universal bases that differs from the one proposed by Preparata et al. (1999). We give a simple algorithm that uses spectra from such chips to reconstruct with high probability random sequences of length lower only by a squared log factor compared to the information theoretic bound. Our algorithm is very robust to errors and has a provable performance even if there are both false negative and false positive errors. Simulations indicate that its sensitivity to errors is also very small in practice.
DOI: 10.1089/10665270360688138
PubMed: 12935339
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: 002439
- to stream PubMed, to step Curation: 002439
- to stream PubMed, to step Checkpoint: 002319
Links to Exploration step
pubmed:12935339Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Handling long targets and errors in sequencing by hybridization.</title>
<author><name sortKey="Halperin, Eran" sort="Halperin, Eran" uniqKey="Halperin E" first="Eran" last="Halperin">Eran Halperin</name>
<affiliation wicri:level="2"><nlm:affiliation>CS Division, Soda Hall, University of California at Berkeley, Berkeley, CA 94720-1776, USA.</nlm:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>CS Division, Soda Hall, University of California at Berkeley, Berkeley, CA 94720-1776</wicri:regionArea>
<placeName><region type="state">Californie</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Halperin, Shay" sort="Halperin, Shay" uniqKey="Halperin S" first="Shay" last="Halperin">Shay Halperin</name>
</author>
<author><name sortKey="Hartman, Tzvika" sort="Hartman, Tzvika" uniqKey="Hartman T" first="Tzvika" last="Hartman">Tzvika Hartman</name>
</author>
<author><name sortKey="Shamir, Ron" sort="Shamir, Ron" uniqKey="Shamir R" first="Ron" last="Shamir">Ron Shamir</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PubMed</idno>
<date when="2003">2003</date>
<idno type="RBID">pubmed:12935339</idno>
<idno type="pmid">12935339</idno>
<idno type="doi">10.1089/10665270360688138</idno>
<idno type="wicri:Area/PubMed/Corpus">002439</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">002439</idno>
<idno type="wicri:Area/PubMed/Curation">002439</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">002439</idno>
<idno type="wicri:Area/PubMed/Checkpoint">002319</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">002319</idno>
<idno type="wicri:Area/Ncbi/Merge">000210</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Handling long targets and errors in sequencing by hybridization.</title>
<author><name sortKey="Halperin, Eran" sort="Halperin, Eran" uniqKey="Halperin E" first="Eran" last="Halperin">Eran Halperin</name>
<affiliation wicri:level="2"><nlm:affiliation>CS Division, Soda Hall, University of California at Berkeley, Berkeley, CA 94720-1776, USA.</nlm:affiliation>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>CS Division, Soda Hall, University of California at Berkeley, Berkeley, CA 94720-1776</wicri:regionArea>
<placeName><region type="state">Californie</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Halperin, Shay" sort="Halperin, Shay" uniqKey="Halperin S" first="Shay" last="Halperin">Shay Halperin</name>
</author>
<author><name sortKey="Hartman, Tzvika" sort="Hartman, Tzvika" uniqKey="Hartman T" first="Tzvika" last="Hartman">Tzvika Hartman</name>
</author>
<author><name sortKey="Shamir, Ron" sort="Shamir, Ron" uniqKey="Shamir R" first="Ron" last="Shamir">Ron Shamir</name>
</author>
</analytic>
<series><title level="j">Journal of computational biology : a journal of computational molecular cell biology</title>
<idno type="ISSN">1066-5277</idno>
<imprint><date when="2003" type="published">2003</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computational Biology (methods)</term>
<term>Data Interpretation, Statistical</term>
<term>Oligonucleotide Array Sequence Analysis (methods)</term>
<term>Sequence Analysis, DNA (methods)</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>Analyse de séquence d'ADN ()</term>
<term>Biologie informatique ()</term>
<term>Interprétation statistique de données</term>
<term>Séquençage par oligonucléotides en batterie ()</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term>
<term>Oligonucleotide Array Sequence Analysis</term>
<term>Sequence Analysis, DNA</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Data Interpretation, Statistical</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Analyse de séquence d'ADN</term>
<term>Biologie informatique</term>
<term>Interprétation statistique de données</term>
<term>Séquençage par oligonucléotides en batterie</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Sequencing by hybridization (SBH) is a DNA sequencing technique, in which the sequence is reconstructed using its k-mer content. This content, which is called the spectrum of the sequence, is obtained by hybridization to a universal DNA array. Standard universal arrays contain all k-mers for some fixed k, typically 8 to 10. Currently, in spite of its promise and elegance, SBH is not competitive with standard gel-based sequencing methods. This is due to two main reasons: lack of tools to handle realistic levels of hybridization errors and an inherent limitation on the length of uniquely reconstructible sequence by standard universal arrays. In this paper, we deal with both problems. We introduce a simple polynomial reconstruction algorithm which can be applied to spectra from standard arrays and has provable performance in the presence of both false negative and false positive errors. We also propose a novel design of chips containing universal bases that differs from the one proposed by Preparata et al. (1999). We give a simple algorithm that uses spectra from such chips to reconstruct with high probability random sequences of length lower only by a squared log factor compared to the information theoretic bound. Our algorithm is very robust to errors and has a provable performance even if there are both false negative and false positive errors. Simulations indicate that its sensitivity to errors is also very small in practice.</div>
</front>
</TEI>
<pubmed><MedlineCitation Status="MEDLINE" Owner="NLM"><PMID Version="1">12935339</PMID>
<DateCompleted><Year>2004</Year>
<Month>03</Month>
<Day>30</Day>
</DateCompleted>
<DateRevised><Year>2006</Year>
<Month>11</Month>
<Day>15</Day>
</DateRevised>
<Article PubModel="Print"><Journal><ISSN IssnType="Print">1066-5277</ISSN>
<JournalIssue CitedMedium="Print"><Volume>10</Volume>
<Issue>3-4</Issue>
<PubDate><Year>2003</Year>
</PubDate>
</JournalIssue>
<Title>Journal of computational biology : a journal of computational molecular cell biology</Title>
<ISOAbbreviation>J. Comput. Biol.</ISOAbbreviation>
</Journal>
<ArticleTitle>Handling long targets and errors in sequencing by hybridization.</ArticleTitle>
<Pagination><MedlinePgn>483-97</MedlinePgn>
</Pagination>
<Abstract><AbstractText>Sequencing by hybridization (SBH) is a DNA sequencing technique, in which the sequence is reconstructed using its k-mer content. This content, which is called the spectrum of the sequence, is obtained by hybridization to a universal DNA array. Standard universal arrays contain all k-mers for some fixed k, typically 8 to 10. Currently, in spite of its promise and elegance, SBH is not competitive with standard gel-based sequencing methods. This is due to two main reasons: lack of tools to handle realistic levels of hybridization errors and an inherent limitation on the length of uniquely reconstructible sequence by standard universal arrays. In this paper, we deal with both problems. We introduce a simple polynomial reconstruction algorithm which can be applied to spectra from standard arrays and has provable performance in the presence of both false negative and false positive errors. We also propose a novel design of chips containing universal bases that differs from the one proposed by Preparata et al. (1999). We give a simple algorithm that uses spectra from such chips to reconstruct with high probability random sequences of length lower only by a squared log factor compared to the information theoretic bound. Our algorithm is very robust to errors and has a provable performance even if there are both false negative and false positive errors. Simulations indicate that its sensitivity to errors is also very small in practice.</AbstractText>
</Abstract>
<AuthorList CompleteYN="Y"><Author ValidYN="Y"><LastName>Halperin</LastName>
<ForeName>Eran</ForeName>
<Initials>E</Initials>
<AffiliationInfo><Affiliation>CS Division, Soda Hall, University of California at Berkeley, Berkeley, CA 94720-1776, USA.</Affiliation>
</AffiliationInfo>
</Author>
<Author ValidYN="Y"><LastName>Halperin</LastName>
<ForeName>Shay</ForeName>
<Initials>S</Initials>
</Author>
<Author ValidYN="Y"><LastName>Hartman</LastName>
<ForeName>Tzvika</ForeName>
<Initials>T</Initials>
</Author>
<Author ValidYN="Y"><LastName>Shamir</LastName>
<ForeName>Ron</ForeName>
<Initials>R</Initials>
</Author>
</AuthorList>
<Language>eng</Language>
<PublicationTypeList><PublicationType UI="D016428">Journal Article</PublicationType>
<PublicationType UI="D013485">Research Support, Non-U.S. Gov't</PublicationType>
<PublicationType UI="D013486">Research Support, U.S. Gov't, Non-P.H.S.</PublicationType>
</PublicationTypeList>
</Article>
<MedlineJournalInfo><Country>United States</Country>
<MedlineTA>J Comput Biol</MedlineTA>
<NlmUniqueID>9433358</NlmUniqueID>
<ISSNLinking>1066-5277</ISSNLinking>
</MedlineJournalInfo>
<CitationSubset>IM</CitationSubset>
<MeshHeadingList><MeshHeading><DescriptorName UI="D019295" MajorTopicYN="N">Computational Biology</DescriptorName>
<QualifierName UI="Q000379" MajorTopicYN="Y">methods</QualifierName>
</MeshHeading>
<MeshHeading><DescriptorName UI="D003627" MajorTopicYN="Y">Data Interpretation, Statistical</DescriptorName>
</MeshHeading>
<MeshHeading><DescriptorName UI="D020411" MajorTopicYN="N">Oligonucleotide Array Sequence Analysis</DescriptorName>
<QualifierName UI="Q000379" MajorTopicYN="Y">methods</QualifierName>
</MeshHeading>
<MeshHeading><DescriptorName UI="D017422" MajorTopicYN="N">Sequence Analysis, DNA</DescriptorName>
<QualifierName UI="Q000379" MajorTopicYN="Y">methods</QualifierName>
</MeshHeading>
</MeshHeadingList>
</MedlineCitation>
<PubmedData><History><PubMedPubDate PubStatus="pubmed"><Year>2003</Year>
<Month>8</Month>
<Day>26</Day>
<Hour>5</Hour>
<Minute>0</Minute>
</PubMedPubDate>
<PubMedPubDate PubStatus="medline"><Year>2004</Year>
<Month>3</Month>
<Day>31</Day>
<Hour>5</Hour>
<Minute>0</Minute>
</PubMedPubDate>
<PubMedPubDate PubStatus="entrez"><Year>2003</Year>
<Month>8</Month>
<Day>26</Day>
<Hour>5</Hour>
<Minute>0</Minute>
</PubMedPubDate>
</History>
<PublicationStatus>ppublish</PublicationStatus>
<ArticleIdList><ArticleId IdType="pubmed">12935339</ArticleId>
<ArticleId IdType="doi">10.1089/10665270360688138</ArticleId>
</ArticleIdList>
</PubmedData>
</pubmed>
<affiliations><list><country><li>États-Unis</li>
</country>
<region><li>Californie</li>
</region>
</list>
<tree><noCountry><name sortKey="Halperin, Shay" sort="Halperin, Shay" uniqKey="Halperin S" first="Shay" last="Halperin">Shay Halperin</name>
<name sortKey="Hartman, Tzvika" sort="Hartman, Tzvika" uniqKey="Hartman T" first="Tzvika" last="Hartman">Tzvika Hartman</name>
<name sortKey="Shamir, Ron" sort="Shamir, Ron" uniqKey="Shamir R" first="Ron" last="Shamir">Ron Shamir</name>
</noCountry>
<country name="États-Unis"><region name="Californie"><name sortKey="Halperin, Eran" sort="Halperin, Eran" uniqKey="Halperin E" first="Eran" last="Halperin">Eran Halperin</name>
</region>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Ncbi/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000210 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd -nk 000210 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Ncbi |étape= Merge |type= RBID |clé= pubmed:12935339 |texte= Handling long targets and errors in sequencing by hybridization. }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/RBID.i -Sk "pubmed:12935339" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
This area was generated with Dilib version V0.6.33. |