SpeedHap: an accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage.
Identifieur interne : 000607 ( Ncbi/Checkpoint ); précédent : 000606; suivant : 000608SpeedHap: an accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage.
Auteurs : Loredana M. Genovese [Italie] ; Filippo Geraci ; Marco PellegriniSource :
- IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM [ 1557-9964 ]
Descripteurs français
- KwdFr :
- Algorithmes, Analyse de mutations d'ADN (), Analyse de séquence d'ADN (), Cartographie chromosomique (), Données de séquences moléculaires, Haplotypes (génétique), Humains, Logiciel, Polymorphisme de nucléotide simple (génétique), Reproductibilité des résultats, Sensibilité et spécificité, Séquence nucléotidique.
- MESH :
English descriptors
- KwdEn :
- MESH :
Abstract
Single nucleotide polymorphism (SNP) is the most frequent form of DNA variation. The set of SNP's present in a chromosome (called the haplotype) is of interest in a wide area of applications in molecular biology and biomedicine, including diagnostic and medical therapy. In this paper we propose a new heuristic method for the problem of haplotype reconstruction for (portions of) a pair of homologous human chromosomes from a single individual (SIH). The problem is well known in literature and exact algorithms have been proposed for the case when no (or few) gaps are allowed in the input fragments. These algorithms, though exact and of polynomial complexity, are slow in practice. When gaps are considered no exact method of polynomial complexity is known. The problem is also hard to approximate with guarantees. Therefore fast heuristics have been proposed. In this paper we describe SpeedHap, a new heuristic method that is able to tackle the case of many gapped fragments and retains its effectiveness even when the input fragments have high rate of reading errors (up to 20%) and low coverage (as low as 3). We test SpeedHap on real data from the HapMap Project.
DOI: 10.1109/TCBB.2008.67
PubMed: 18989037
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: 000384
- to stream PubMed, to step Curation: 000384
- to stream PubMed, to step Checkpoint: 000384
- to stream Ncbi, to step Merge: 000607
- to stream Ncbi, to step Curation: 000607
Links to Exploration step
pubmed:18989037Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">SpeedHap: an accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage.</title><author><name sortKey="Genovese, Loredana M" sort="Genovese, Loredana M" uniqKey="Genovese L" first="Loredana M" last="Genovese">Loredana M. Genovese</name><affiliation wicri:level="1"><nlm:affiliation>Institute for Informatics and Telematics, Italian National Research Council, Via G. Moruzzi 1, 56124 Pisa, Italy. loredana.genovese@gmail.com</nlm:affiliation><country xml:lang="fr">Italie</country><wicri:regionArea>Institute for Informatics and Telematics, Italian National Research Council, Via G. Moruzzi 1, 56124 Pisa</wicri:regionArea><placeName><settlement type="city">Pise</settlement><region nuts="2">Toscane</region></placeName></affiliation></author><author><name sortKey="Geraci, Filippo" sort="Geraci, Filippo" uniqKey="Geraci F" first="Filippo" last="Geraci">Filippo Geraci</name></author><author><name sortKey="Pellegrini, Marco" sort="Pellegrini, Marco" uniqKey="Pellegrini M" first="Marco" last="Pellegrini">Marco Pellegrini</name></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="????"><PubDate><MedlineDate>2008 Oct-Dec</MedlineDate></PubDate></date><idno type="doi">10.1109/TCBB.2008.67</idno><idno type="RBID">pubmed:18989037</idno><idno type="pmid">18989037</idno><idno type="wicri:Area/PubMed/Corpus">000384</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000384</idno><idno type="wicri:Area/PubMed/Curation">000384</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000384</idno><idno type="wicri:Area/PubMed/Checkpoint">000384</idno><idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000384</idno><idno type="wicri:Area/Ncbi/Merge">000607</idno><idno type="wicri:Area/Ncbi/Curation">000607</idno><idno type="wicri:Area/Ncbi/Checkpoint">000607</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">SpeedHap: an accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage.</title><author><name sortKey="Genovese, Loredana M" sort="Genovese, Loredana M" uniqKey="Genovese L" first="Loredana M" last="Genovese">Loredana M. Genovese</name><affiliation wicri:level="1"><nlm:affiliation>Institute for Informatics and Telematics, Italian National Research Council, Via G. Moruzzi 1, 56124 Pisa, Italy. loredana.genovese@gmail.com</nlm:affiliation><country xml:lang="fr">Italie</country><wicri:regionArea>Institute for Informatics and Telematics, Italian National Research Council, Via G. Moruzzi 1, 56124 Pisa</wicri:regionArea><placeName><settlement type="city">Pise</settlement><region nuts="2">Toscane</region></placeName></affiliation></author><author><name sortKey="Geraci, Filippo" sort="Geraci, Filippo" uniqKey="Geraci F" first="Filippo" last="Geraci">Filippo Geraci</name></author><author><name sortKey="Pellegrini, Marco" sort="Pellegrini, Marco" uniqKey="Pellegrini M" first="Marco" last="Pellegrini">Marco Pellegrini</name></author></analytic><series><title level="j">IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM</title><idno type="eISSN">1557-9964</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Base Sequence</term><term>Chromosome Mapping (methods)</term><term>DNA Mutational Analysis (methods)</term><term>Haplotypes (genetics)</term><term>Humans</term><term>Molecular Sequence Data</term><term>Polymorphism, Single Nucleotide (genetics)</term><term>Reproducibility of Results</term><term>Sensitivity and Specificity</term><term>Sequence Analysis, DNA (methods)</term><term>Software</term></keywords><keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term><term>Analyse de mutations d'ADN ()</term><term>Analyse de séquence d'ADN ()</term><term>Cartographie chromosomique ()</term><term>Données de séquences moléculaires</term><term>Haplotypes (génétique)</term><term>Humains</term><term>Logiciel</term><term>Polymorphisme de nucléotide simple (génétique)</term><term>Reproductibilité des résultats</term><term>Sensibilité et spécificité</term><term>Séquence nucléotidique</term></keywords><keywords scheme="MESH" qualifier="genetics" xml:lang="en"><term>Haplotypes</term><term>Polymorphism, Single Nucleotide</term></keywords><keywords scheme="MESH" qualifier="génétique" xml:lang="fr"><term>Haplotypes</term><term>Polymorphisme de nucléotide simple</term></keywords><keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Chromosome Mapping</term><term>DNA Mutational Analysis</term><term>Sequence Analysis, DNA</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Algorithms</term><term>Base Sequence</term><term>Humans</term><term>Molecular Sequence Data</term><term>Reproducibility of Results</term><term>Sensitivity and Specificity</term><term>Software</term></keywords><keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term><term>Analyse de mutations d'ADN</term><term>Analyse de séquence d'ADN</term><term>Cartographie chromosomique</term><term>Données de séquences moléculaires</term><term>Humains</term><term>Logiciel</term><term>Reproductibilité des résultats</term><term>Sensibilité et spécificité</term><term>Séquence nucléotidique</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Single nucleotide polymorphism (SNP) is the most frequent form of DNA variation. The set of SNP's present in a chromosome (called the haplotype) is of interest in a wide area of applications in molecular biology and biomedicine, including diagnostic and medical therapy. In this paper we propose a new heuristic method for the problem of haplotype reconstruction for (portions of) a pair of homologous human chromosomes from a single individual (SIH). The problem is well known in literature and exact algorithms have been proposed for the case when no (or few) gaps are allowed in the input fragments. These algorithms, though exact and of polynomial complexity, are slow in practice. When gaps are considered no exact method of polynomial complexity is known. The problem is also hard to approximate with guarantees. Therefore fast heuristics have been proposed. In this paper we describe SpeedHap, a new heuristic method that is able to tackle the case of many gapped fragments and retains its effectiveness even when the input fragments have high rate of reading errors (up to 20%) and low coverage (as low as 3). We test SpeedHap on real data from the HapMap Project.</div></front></TEI><affiliations><list><country><li>Italie</li></country><region><li>Toscane</li></region><settlement><li>Pise</li></settlement></list><tree><noCountry><name sortKey="Geraci, Filippo" sort="Geraci, Filippo" uniqKey="Geraci F" first="Filippo" last="Geraci">Filippo Geraci</name><name sortKey="Pellegrini, Marco" sort="Pellegrini, Marco" uniqKey="Pellegrini M" first="Marco" last="Pellegrini">Marco Pellegrini</name></noCountry><country name="Italie"><region name="Toscane"><name sortKey="Genovese, Loredana M" sort="Genovese, Loredana M" uniqKey="Genovese L" first="Loredana M" last="Genovese">Loredana M. Genovese</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/TelematiV1/Data/Ncbi/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000607 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Ncbi/Checkpoint/biblio.hfd -nk 000607 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= TelematiV1
|flux= Ncbi
|étape= Checkpoint
|type= RBID
|clé= pubmed:18989037
|texte= SpeedHap: an accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Ncbi/Checkpoint/RBID.i -Sk "pubmed:18989037" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Ncbi/Checkpoint/biblio.hfd \
| NlmPubMed2Wicri -a TelematiV1
| This area was generated with Dilib version V0.6.31. |  |