Improved hit criteria for DNA local alignment
Identifieur interne : 000010 ( Ncbi/Merge ); précédent : 000009; suivant : 000011Improved hit criteria for DNA local alignment
Auteurs : Laurent Noé ; Gregory KucherovSource :
- BMC Bioinformatics [ 1471-2105 ] ; 2004.
Descripteurs français
- KwdFr :
- ADN (génétique), ADN bactérien (génétique), ADN fongique (génétique), Algorithmes, Alignement de séquences (), Alignement de séquences (normes), Animaux, Chaines de Markov, Chromosomes X humains (génétique), Drosophila (génétique), Humains, Modèles statistiques, Neisseria meningitidis (génétique), Saccharomyces cerevisiae (génétique).
- MESH :
English descriptors
- KwdEn :
- Algorithms, Animals, Chromosomes, Human, X (genetics), DNA (genetics), DNA, Bacterial (genetics), DNA, Fungal (genetics), Drosophila (genetics), Humans, Markov Chains, Models, Statistical, Neisseria meningitidis (genetics), Saccharomyces cerevisiae (genetics), Sequence Alignment (methods), Sequence Alignment (standards).
- MESH :
- chemical , genetics : DNA, DNA, Bacterial, DNA, Fungal.
- genetics : Chromosomes, Human, X, Drosophila, Neisseria meningitidis, Saccharomyces cerevisiae.
- methods : Sequence Alignment.
- standards : Sequence Alignment.
- Algorithms, Animals, Humans, Markov Chains, Models, Statistical.
Abstract
The hit criterion is a key component of heuristic local alignment algorithms. It specifies a class of patterns assumed to witness a potential similarity, and this choice is decisive for the selectivity and sensitivity of the whole method.
In this paper, we propose two ways to improve the hit criterion. First, we define the
Proposed algorithmic ideas allow to obtain a significant gain in sensitivity of similarity search without increase in execution time. The method has been implemented in YASS software available at
Url:
DOI: 10.1186/1471-2105-5-149
PubMed: 15485572
PubMed Central: 526756
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 000024
- to stream Pmc, to step Curation: 000024
- to stream Pmc, to step Checkpoint: 000097
- to stream PubMed, to step Corpus: 000177
- to stream PubMed, to step Curation: 000177
- to stream PubMed, to step Checkpoint: 000162
Links to Exploration step
PMC:526756Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Improved hit criteria for DNA local alignment</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">15485572</idno>
<idno type="pmc">526756</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC526756</idno>
<idno type="RBID">PMC:526756</idno>
<idno type="doi">10.1186/1471-2105-5-149</idno>
<date when="2004">2004</date>
<idno type="wicri:Area/Pmc/Corpus">000024</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000024</idno>
<idno type="wicri:Area/Pmc/Curation">000024</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000024</idno>
<idno type="wicri:Area/Pmc/Checkpoint">000097</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">000097</idno>
<idno type="wicri:source">PubMed</idno>
<idno type="wicri:Area/PubMed/Corpus">000177</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000177</idno>
<idno type="wicri:Area/PubMed/Curation">000177</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000177</idno>
<idno type="wicri:Area/PubMed/Checkpoint">000162</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000162</idno>
<idno type="wicri:Area/Ncbi/Merge">000010</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Improved hit criteria for DNA local alignment</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2004">2004</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Animals</term>
<term>Chromosomes, Human, X (genetics)</term>
<term>DNA (genetics)</term>
<term>DNA, Bacterial (genetics)</term>
<term>DNA, Fungal (genetics)</term>
<term>Drosophila (genetics)</term>
<term>Humans</term>
<term>Markov Chains</term>
<term>Models, Statistical</term>
<term>Neisseria meningitidis (genetics)</term>
<term>Saccharomyces cerevisiae (genetics)</term>
<term>Sequence Alignment (methods)</term>
<term>Sequence Alignment (standards)</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>ADN (génétique)</term>
<term>ADN bactérien (génétique)</term>
<term>ADN fongique (génétique)</term>
<term>Algorithmes</term>
<term>Alignement de séquences ()</term>
<term>Alignement de séquences (normes)</term>
<term>Animaux</term>
<term>Chaines de Markov</term>
<term>Chromosomes X humains (génétique)</term>
<term>Drosophila (génétique)</term>
<term>Humains</term>
<term>Modèles statistiques</term>
<term>Neisseria meningitidis (génétique)</term>
<term>Saccharomyces cerevisiae (génétique)</term>
</keywords>
<keywords scheme="MESH" type="chemical" qualifier="genetics" xml:lang="en"><term>DNA</term>
<term>DNA, Bacterial</term>
<term>DNA, Fungal</term>
</keywords>
<keywords scheme="MESH" qualifier="genetics" xml:lang="en"><term>Chromosomes, Human, X</term>
<term>Drosophila</term>
<term>Neisseria meningitidis</term>
<term>Saccharomyces cerevisiae</term>
</keywords>
<keywords scheme="MESH" qualifier="génétique" xml:lang="fr"><term>ADN</term>
<term>ADN bactérien</term>
<term>ADN fongique</term>
<term>Chromosomes X humains</term>
<term>Drosophila</term>
<term>Neisseria meningitidis</term>
<term>Saccharomyces cerevisiae</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Sequence Alignment</term>
</keywords>
<keywords scheme="MESH" qualifier="normes" xml:lang="fr"><term>Alignement de séquences</term>
</keywords>
<keywords scheme="MESH" qualifier="standards" xml:lang="en"><term>Sequence Alignment</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Animals</term>
<term>Humans</term>
<term>Markov Chains</term>
<term>Models, Statistical</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term>
<term>Alignement de séquences</term>
<term>Animaux</term>
<term>Chaines de Markov</term>
<term>Humains</term>
<term>Modèles statistiques</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>The hit criterion is a key component of heuristic local alignment algorithms. It specifies a class of patterns assumed to witness a potential similarity, and this choice is decisive for the selectivity and sensitivity of the whole method.</p>
</sec>
<sec><title>Results</title>
<p>In this paper, we propose two ways to improve the hit criterion. First, we define the <italic>group criterion </italic>
combining the advantages of the single-seed and double-seed approaches used in existing algorithms. Second, we introduce <italic>transition-constrained seeds </italic>
that extend spaced seeds by the possibility of distinguishing transition and transversion mismatches. We provide analytical data as well as experimental results, obtained with the YASS software, supporting both improvements.</p>
</sec>
<sec><title>Conclusions</title>
<p>Proposed algorithmic ideas allow to obtain a significant gain in sensitivity of similarity search without increase in execution time. The method has been implemented in YASS software available at <ext-link ext-link-type="uri" xlink:href="http://www.loria.fr/projects/YASS/"></ext-link>
.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<double pmid="15485572"><pmc><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Improved hit criteria for DNA local alignment</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">15485572</idno>
<idno type="pmc">526756</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC526756</idno>
<idno type="RBID">PMC:526756</idno>
<idno type="doi">10.1186/1471-2105-5-149</idno>
<date when="2004">2004</date>
<idno type="wicri:Area/Pmc/Corpus">000024</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000024</idno>
<idno type="wicri:Area/Pmc/Curation">000024</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000024</idno>
<idno type="wicri:Area/Pmc/Checkpoint">000097</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">000097</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Improved hit criteria for DNA local alignment</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2004">2004</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>The hit criterion is a key component of heuristic local alignment algorithms. It specifies a class of patterns assumed to witness a potential similarity, and this choice is decisive for the selectivity and sensitivity of the whole method.</p>
</sec>
<sec><title>Results</title>
<p>In this paper, we propose two ways to improve the hit criterion. First, we define the <italic>group criterion </italic>
combining the advantages of the single-seed and double-seed approaches used in existing algorithms. Second, we introduce <italic>transition-constrained seeds </italic>
that extend spaced seeds by the possibility of distinguishing transition and transversion mismatches. We provide analytical data as well as experimental results, obtained with the YASS software, supporting both improvements.</p>
</sec>
<sec><title>Conclusions</title>
<p>Proposed algorithmic ideas allow to obtain a significant gain in sensitivity of similarity search without increase in execution time. The method has been implemented in YASS software available at <ext-link ext-link-type="uri" xlink:href="http://www.loria.fr/projects/YASS/"></ext-link>
.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
</listBibl>
</div1>
</back>
</TEI>
</pmc>
<pubmed><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Improved hit criteria for DNA local alignment.</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation wicri:level="1"><nlm:affiliation>LORIA/INRIA-Lorraine, Villers-lès-Nancy France. Laurent.Noe@loria.fr</nlm:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PubMed</idno>
<date when="2004">2004</date>
<idno type="doi">10.1186/1471-2105-5-149</idno>
<idno type="RBID">pubmed:15485572</idno>
<idno type="pmid">15485572</idno>
<idno type="wicri:Area/PubMed/Corpus">000177</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000177</idno>
<idno type="wicri:Area/PubMed/Curation">000177</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000177</idno>
<idno type="wicri:Area/PubMed/Checkpoint">000162</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000162</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Improved hit criteria for DNA local alignment.</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation wicri:level="1"><nlm:affiliation>LORIA/INRIA-Lorraine, Villers-lès-Nancy France. Laurent.Noe@loria.fr</nlm:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
</author>
</analytic>
<series><title level="j">BMC bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2004" type="published">2004</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Animals</term>
<term>Chromosomes, Human, X (genetics)</term>
<term>DNA (genetics)</term>
<term>DNA, Bacterial (genetics)</term>
<term>DNA, Fungal (genetics)</term>
<term>Drosophila (genetics)</term>
<term>Humans</term>
<term>Markov Chains</term>
<term>Models, Statistical</term>
<term>Neisseria meningitidis (genetics)</term>
<term>Saccharomyces cerevisiae (genetics)</term>
<term>Sequence Alignment (methods)</term>
<term>Sequence Alignment (standards)</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>ADN (génétique)</term>
<term>ADN bactérien (génétique)</term>
<term>ADN fongique (génétique)</term>
<term>Algorithmes</term>
<term>Alignement de séquences ()</term>
<term>Alignement de séquences (normes)</term>
<term>Animaux</term>
<term>Chaines de Markov</term>
<term>Chromosomes X humains (génétique)</term>
<term>Drosophila (génétique)</term>
<term>Humains</term>
<term>Modèles statistiques</term>
<term>Neisseria meningitidis (génétique)</term>
<term>Saccharomyces cerevisiae (génétique)</term>
</keywords>
<keywords scheme="MESH" type="chemical" qualifier="genetics" xml:lang="en"><term>DNA</term>
<term>DNA, Bacterial</term>
<term>DNA, Fungal</term>
</keywords>
<keywords scheme="MESH" qualifier="genetics" xml:lang="en"><term>Chromosomes, Human, X</term>
<term>Drosophila</term>
<term>Neisseria meningitidis</term>
<term>Saccharomyces cerevisiae</term>
</keywords>
<keywords scheme="MESH" qualifier="génétique" xml:lang="fr"><term>ADN</term>
<term>ADN bactérien</term>
<term>ADN fongique</term>
<term>Chromosomes X humains</term>
<term>Drosophila</term>
<term>Neisseria meningitidis</term>
<term>Saccharomyces cerevisiae</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Sequence Alignment</term>
</keywords>
<keywords scheme="MESH" qualifier="normes" xml:lang="fr"><term>Alignement de séquences</term>
</keywords>
<keywords scheme="MESH" qualifier="standards" xml:lang="en"><term>Sequence Alignment</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Animals</term>
<term>Humans</term>
<term>Markov Chains</term>
<term>Models, Statistical</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term>
<term>Alignement de séquences</term>
<term>Animaux</term>
<term>Chaines de Markov</term>
<term>Humains</term>
<term>Modèles statistiques</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The hit criterion is a key component of heuristic local alignment algorithms. It specifies a class of patterns assumed to witness a potential similarity, and this choice is decisive for the selectivity and sensitivity of the whole method.</div>
</front>
</TEI>
</pubmed>
</double>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Ncbi/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000010 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd -nk 000010 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Ncbi |étape= Merge |type= RBID |clé= PMC:526756 |texte= Improved hit criteria for DNA local alignment }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/RBID.i -Sk "pubmed:15485572" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd \ | NlmPubMed2Wicri -a InforLorV4
This area was generated with Dilib version V0.6.33. |