Optimizing Spaced k-mer Neighbors for Efficient Filtration in Protein Similarity Search.
Identifieur interne : 005393 ( Main/Exploration ); précédent : 005392; suivant : 005394Optimizing Spaced k-mer Neighbors for Efficient Filtration in Protein Similarity Search.
Auteurs : Weiming Li ; Bin Ma ; Kaizhong ZhangSource :
- IEEE/ACM transactions on computational biology and bioinformatics [ 1557-9964 ]
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
- chemical , chemistry : Proteins.
- chemical , genetics : Proteins.
- methods : Computational Biology, Sequence Analysis, Protein.
- Algorithms, Animals, Drosophila, Humans, Mice, Sequence Homology, Amino Acid, Software.
Abstract
Large-scale comparison or similarity search of genomic DNA and protein sequence is of fundamental importance in modern molecular biology. To perform DNA and protein sequence similarity search efficiently, seeding (or filtration) method has been widely used where only sequences sharing a common pattern or "seed" are subject to detailed comparison. Therefore these methods trade search sensitivity with search speed. In this paper, we introduce a new seeding method, called spaced k-mer neighbors, which provides a better tradeoff between the sensitivity and speed in protein sequence similarity search. With the method of spaced k-mer neighbors, for each spaced k-mer, a set of spaced k-mers is selected as its neighbors. These pre-selected spaced k-mer neighbors are then used to detect hits between query sequence and database sequences. We propose an efficient heuristic algorithm for the spaced neighbor selection. Our computational experimental results demonstrate that the method of spaced k-mer neighbors can improve the overall tradeoff efficiency over existing seeding methods.
DOI: 10.1109/TCBB.2014.2306831
PubMed: 26355786
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: 001A41
- to stream PubMed, to step Curation: 001A41
- to stream PubMed, to step Checkpoint: 002A69
- to stream Ncbi, to step Merge: 001264
- to stream Ncbi, to step Curation: 001264
- to stream Ncbi, to step Checkpoint: 001264
- to stream Main, to step Merge: 005473
- to stream Main, to step Curation: 005393
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Optimizing Spaced k-mer Neighbors for Efficient Filtration in Protein Similarity Search.</title>
<author><name sortKey="Li, Weiming" sort="Li, Weiming" uniqKey="Li W" first="Weiming" last="Li">Weiming Li</name>
</author>
<author><name sortKey="Ma, Bin" sort="Ma, Bin" uniqKey="Ma B" first="Bin" last="Ma">Bin Ma</name>
</author>
<author><name sortKey="Zhang, Kaizhong" sort="Zhang, Kaizhong" uniqKey="Zhang K" first="Kaizhong" last="Zhang">Kaizhong Zhang</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PubMed</idno>
<date when="????"><PubDate><MedlineDate>2014 Mar-Apr</MedlineDate>
</PubDate>
</date>
<idno type="RBID">pubmed:26355786</idno>
<idno type="pmid">26355786</idno>
<idno type="doi">10.1109/TCBB.2014.2306831</idno>
<idno type="wicri:Area/PubMed/Corpus">001A41</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">001A41</idno>
<idno type="wicri:Area/PubMed/Curation">001A41</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">001A41</idno>
<idno type="wicri:Area/PubMed/Checkpoint">002A69</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">002A69</idno>
<idno type="wicri:Area/Ncbi/Merge">001264</idno>
<idno type="wicri:Area/Ncbi/Curation">001264</idno>
<idno type="wicri:Area/Ncbi/Checkpoint">001264</idno>
<idno type="wicri:Area/Main/Merge">005473</idno>
<idno type="wicri:Area/Main/Curation">005393</idno>
<idno type="wicri:Area/Main/Exploration">005393</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Optimizing Spaced k-mer Neighbors for Efficient Filtration in Protein Similarity Search.</title>
<author><name sortKey="Li, Weiming" sort="Li, Weiming" uniqKey="Li W" first="Weiming" last="Li">Weiming Li</name>
</author>
<author><name sortKey="Ma, Bin" sort="Ma, Bin" uniqKey="Ma B" first="Bin" last="Ma">Bin Ma</name>
</author>
<author><name sortKey="Zhang, Kaizhong" sort="Zhang, Kaizhong" uniqKey="Zhang K" first="Kaizhong" last="Zhang">Kaizhong Zhang</name>
</author>
</analytic>
<series><title level="j">IEEE/ACM transactions on computational biology and bioinformatics</title>
<idno type="eISSN">1557-9964</idno>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Animals</term>
<term>Computational Biology (methods)</term>
<term>Drosophila</term>
<term>Humans</term>
<term>Mice</term>
<term>Proteins (chemistry)</term>
<term>Proteins (genetics)</term>
<term>Sequence Analysis, Protein (methods)</term>
<term>Sequence Homology, Amino Acid</term>
<term>Software</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term>
<term>Analyse de séquence de protéine ()</term>
<term>Animaux</term>
<term>Biologie informatique ()</term>
<term>Drosophila</term>
<term>Humains</term>
<term>Logiciel</term>
<term>Protéines ()</term>
<term>Protéines (génétique)</term>
<term>Similitude de séquences d'acides aminés</term>
<term>Souris</term>
</keywords>
<keywords scheme="MESH" type="chemical" qualifier="chemistry" xml:lang="en"><term>Proteins</term>
</keywords>
<keywords scheme="MESH" type="chemical" qualifier="genetics" xml:lang="en"><term>Proteins</term>
</keywords>
<keywords scheme="MESH" qualifier="génétique" xml:lang="fr"><term>Protéines</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term>
<term>Sequence Analysis, Protein</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Animals</term>
<term>Drosophila</term>
<term>Humans</term>
<term>Mice</term>
<term>Sequence Homology, Amino Acid</term>
<term>Software</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term>
<term>Analyse de séquence de protéine</term>
<term>Animaux</term>
<term>Biologie informatique</term>
<term>Drosophila</term>
<term>Humains</term>
<term>Logiciel</term>
<term>Protéines</term>
<term>Similitude de séquences d'acides aminés</term>
<term>Souris</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Large-scale comparison or similarity search of genomic DNA and protein sequence is of fundamental importance in modern molecular biology. To perform DNA and protein sequence similarity search efficiently, seeding (or filtration) method has been widely used where only sequences sharing a common pattern or "seed" are subject to detailed comparison. Therefore these methods trade search sensitivity with search speed. In this paper, we introduce a new seeding method, called spaced k-mer neighbors, which provides a better tradeoff between the sensitivity and speed in protein sequence similarity search. With the method of spaced k-mer neighbors, for each spaced k-mer, a set of spaced k-mers is selected as its neighbors. These pre-selected spaced k-mer neighbors are then used to detect hits between query sequence and database sequences. We propose an efficient heuristic algorithm for the spaced neighbor selection. Our computational experimental results demonstrate that the method of spaced k-mer neighbors can improve the overall tradeoff efficiency over existing seeding methods. </div>
</front>
</TEI>
<affiliations><list></list>
<tree><noCountry><name sortKey="Li, Weiming" sort="Li, Weiming" uniqKey="Li W" first="Weiming" last="Li">Weiming Li</name>
<name sortKey="Ma, Bin" sort="Ma, Bin" uniqKey="Ma B" first="Bin" last="Ma">Bin Ma</name>
<name sortKey="Zhang, Kaizhong" sort="Zhang, Kaizhong" uniqKey="Zhang K" first="Kaizhong" last="Zhang">Kaizhong Zhang</name>
</noCountry>
</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 005393 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 005393 | 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é= pubmed:26355786 |texte= Optimizing Spaced k-mer Neighbors for Efficient Filtration in Protein Similarity Search. }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:26355786" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |