Local homology recognition and distance measures in linear time using compressed amino acid alphabets.
Identifieur interne : 002411 ( PubMed/Curation ); précédent : 002410; suivant : 002412Local homology recognition and distance measures in linear time using compressed amino acid alphabets.
Auteurs : Robert C. EdgarSource :
- Nucleic acids research [ 1362-4962 ] ; 2004.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
- chemical , analysis : Amino Acids.
- chemical , chemistry : Proteins.
- methods : Computational Biology, Sequence Alignment.
- Algorithms, Evolution, Molecular, Molecular Sequence Data, Phylogeny, Sequence Homology, Amino Acid, Software, Time Factors.
Abstract
Methods for discovery of local similarities and estimation of evolutionary distance by identifying k-mers (contiguous subsequences of length k) common to two sequences are described. Given unaligned sequences of length L, these methods have O(L) time complexity. The ability of compressed amino acid alphabets to extend these techniques to distantly related proteins was investigated. The performance of these algorithms was evaluated for different alphabets and choices of k using a test set of 1848 pairs of structurally alignable sequences selected from the FSSP database. Distance measures derived from k-mer counting were found to correlate well with percentage identity derived from sequence alignments. Compressed alphabets were seen to improve performance in local similarity discovery, but no evidence was found of improvements when applied to distance estimates. The performance of our local similarity discovery method was compared with the fast Fourier transform (FFT) used in MAFFT, which has O(L log L) time complexity. The method for achieving comparable coverage to FFT is revealed here, and is more than an order of magnitude faster. We suggest using k-mer distance for fast, approximate phylogenetic tree construction, and show that a speed improvement of more than three orders of magnitude can be achieved relative to standard distance methods, which require alignments.
DOI: 10.1093/nar/gkh180
PubMed: 14729922
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: Pour aller vers cette notice dans l'étape Curation :002411
Links to Exploration step
pubmed:14729922Curation
No country items
Robert C. Edgar<affiliation><nlm:affiliation>bob@drive5.com</nlm:affiliation><wicri:noCountry code="no comma">bob@drive5.com</wicri:noCountry></affiliation>Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Local homology recognition and distance measures in linear time using compressed amino acid alphabets.</title><author><name sortKey="Edgar, Robert C" sort="Edgar, Robert C" uniqKey="Edgar R" first="Robert C" last="Edgar">Robert C. Edgar</name><affiliation><nlm:affiliation>bob@drive5.com</nlm:affiliation><wicri:noCountry code="no comma">bob@drive5.com</wicri:noCountry></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2004">2004</date><idno type="RBID">pubmed:14729922</idno><idno type="pmid">14729922</idno><idno type="doi">10.1093/nar/gkh180</idno><idno type="wicri:Area/PubMed/Corpus">002411</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">002411</idno><idno type="wicri:Area/PubMed/Curation">002411</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">002411</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Local homology recognition and distance measures in linear time using compressed amino acid alphabets.</title><author><name sortKey="Edgar, Robert C" sort="Edgar, Robert C" uniqKey="Edgar R" first="Robert C" last="Edgar">Robert C. Edgar</name><affiliation><nlm:affiliation>bob@drive5.com</nlm:affiliation><wicri:noCountry code="no comma">bob@drive5.com</wicri:noCountry></affiliation></author></analytic><series><title level="j">Nucleic acids research</title><idno type="eISSN">1362-4962</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>Amino Acids (analysis)</term><term>Computational Biology (methods)</term><term>Evolution, Molecular</term><term>Molecular Sequence Data</term><term>Phylogeny</term><term>Proteins (chemistry)</term><term>Sequence Alignment (methods)</term><term>Sequence Homology, Amino Acid</term><term>Software</term><term>Time Factors</term></keywords><keywords scheme="KwdFr" xml:lang="fr"><term>Acides aminés (analyse)</term><term>Algorithmes</term><term>Alignement de séquences ()</term><term>Biologie informatique ()</term><term>Données de séquences moléculaires</term><term>Facteurs temps</term><term>Logiciel</term><term>Phylogénie</term><term>Protéines ()</term><term>Similitude de séquences d'acides aminés</term><term>Évolution moléculaire</term></keywords><keywords scheme="MESH" type="chemical" qualifier="analysis" xml:lang="en"><term>Amino Acids</term></keywords><keywords scheme="MESH" type="chemical" qualifier="chemistry" xml:lang="en"><term>Proteins</term></keywords><keywords scheme="MESH" qualifier="analyse" xml:lang="fr"><term>Acides aminés</term></keywords><keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term><term>Sequence Alignment</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Algorithms</term><term>Evolution, Molecular</term><term>Molecular Sequence Data</term><term>Phylogeny</term><term>Sequence Homology, Amino Acid</term><term>Software</term><term>Time Factors</term></keywords><keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term><term>Alignement de séquences</term><term>Biologie informatique</term><term>Données de séquences moléculaires</term><term>Facteurs temps</term><term>Logiciel</term><term>Phylogénie</term><term>Protéines</term><term>Similitude de séquences d'acides aminés</term><term>Évolution moléculaire</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Methods for discovery of local similarities and estimation of evolutionary distance by identifying k-mers (contiguous subsequences of length k) common to two sequences are described. Given unaligned sequences of length L, these methods have O(L) time complexity. The ability of compressed amino acid alphabets to extend these techniques to distantly related proteins was investigated. The performance of these algorithms was evaluated for different alphabets and choices of k using a test set of 1848 pairs of structurally alignable sequences selected from the FSSP database. Distance measures derived from k-mer counting were found to correlate well with percentage identity derived from sequence alignments. Compressed alphabets were seen to improve performance in local similarity discovery, but no evidence was found of improvements when applied to distance estimates. The performance of our local similarity discovery method was compared with the fast Fourier transform (FFT) used in MAFFT, which has O(L log L) time complexity. The method for achieving comparable coverage to FFT is revealed here, and is more than an order of magnitude faster. We suggest using k-mer distance for fast, approximate phylogenetic tree construction, and show that a speed improvement of more than three orders of magnitude can be achieved relative to standard distance methods, which require alignments.</div></front></TEI><pubmed><MedlineCitation Status="MEDLINE" Owner="NLM"><PMID Version="1">14729922</PMID><DateCompleted><Year>2004</Year><Month>02</Month><Day>11</Day></DateCompleted><DateRevised><Year>2018</Year><Month>11</Month><Day>13</Day></DateRevised><Article PubModel="Electronic-Print"><Journal><ISSN IssnType="Electronic">1362-4962</ISSN><JournalIssue CitedMedium="Internet"><Volume>32</Volume><Issue>1</Issue><PubDate><Year>2004</Year></PubDate></JournalIssue><Title>Nucleic acids research</Title><ISOAbbreviation>Nucleic Acids Res.</ISOAbbreviation></Journal><ArticleTitle>Local homology recognition and distance measures in linear time using compressed amino acid alphabets.</ArticleTitle><Pagination><MedlinePgn>380-5</MedlinePgn></Pagination><Abstract><AbstractText>Methods for discovery of local similarities and estimation of evolutionary distance by identifying k-mers (contiguous subsequences of length k) common to two sequences are described. Given unaligned sequences of length L, these methods have O(L) time complexity. The ability of compressed amino acid alphabets to extend these techniques to distantly related proteins was investigated. The performance of these algorithms was evaluated for different alphabets and choices of k using a test set of 1848 pairs of structurally alignable sequences selected from the FSSP database. Distance measures derived from k-mer counting were found to correlate well with percentage identity derived from sequence alignments. Compressed alphabets were seen to improve performance in local similarity discovery, but no evidence was found of improvements when applied to distance estimates. The performance of our local similarity discovery method was compared with the fast Fourier transform (FFT) used in MAFFT, which has O(L log L) time complexity. The method for achieving comparable coverage to FFT is revealed here, and is more than an order of magnitude faster. We suggest using k-mer distance for fast, approximate phylogenetic tree construction, and show that a speed improvement of more than three orders of magnitude can be achieved relative to standard distance methods, which require alignments.</AbstractText></Abstract><AuthorList CompleteYN="Y"><Author ValidYN="Y"><LastName>Edgar</LastName><ForeName>Robert C</ForeName><Initials>RC</Initials><AffiliationInfo><Affiliation>bob@drive5.com</Affiliation></AffiliationInfo></Author></AuthorList><Language>eng</Language><PublicationTypeList><PublicationType UI="D016428">Journal Article</PublicationType></PublicationTypeList><ArticleDate DateType="Electronic"><Year>2004</Year><Month>01</Month><Day>16</Day></ArticleDate></Article><MedlineJournalInfo><Country>England</Country><MedlineTA>Nucleic Acids Res</MedlineTA><NlmUniqueID>0411011</NlmUniqueID><ISSNLinking>0305-1048</ISSNLinking></MedlineJournalInfo><ChemicalList><Chemical><RegistryNumber>0</RegistryNumber><NameOfSubstance UI="D000596">Amino Acids</NameOfSubstance></Chemical><Chemical><RegistryNumber>0</RegistryNumber><NameOfSubstance UI="D011506">Proteins</NameOfSubstance></Chemical></ChemicalList><CitationSubset>IM</CitationSubset><MeshHeadingList><MeshHeading><DescriptorName UI="D000465" MajorTopicYN="N">Algorithms</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D000596" MajorTopicYN="N">Amino Acids</DescriptorName><QualifierName UI="Q000032" MajorTopicYN="Y">analysis</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D019295" MajorTopicYN="N">Computational Biology</DescriptorName><QualifierName UI="Q000379" MajorTopicYN="Y">methods</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D019143" MajorTopicYN="Y">Evolution, Molecular</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D008969" MajorTopicYN="N">Molecular Sequence Data</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D010802" MajorTopicYN="N">Phylogeny</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D011506" MajorTopicYN="N">Proteins</DescriptorName><QualifierName UI="Q000737" MajorTopicYN="N">chemistry</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D016415" MajorTopicYN="N">Sequence Alignment</DescriptorName><QualifierName UI="Q000379" MajorTopicYN="N">methods</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D017386" MajorTopicYN="Y">Sequence Homology, Amino Acid</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D012984" MajorTopicYN="N">Software</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D013997" MajorTopicYN="N">Time Factors</DescriptorName></MeshHeading></MeshHeadingList></MedlineCitation><PubmedData><History><PubMedPubDate PubStatus="pubmed"><Year>2004</Year><Month>1</Month><Day>20</Day><Hour>5</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="medline"><Year>2004</Year><Month>2</Month><Day>12</Day><Hour>5</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="entrez"><Year>2004</Year><Month>1</Month><Day>20</Day><Hour>5</Hour><Minute>0</Minute></PubMedPubDate></History><PublicationStatus>epublish</PublicationStatus><ArticleIdList><ArticleId IdType="pubmed">14729922</ArticleId><ArticleId IdType="doi">10.1093/nar/gkh180</ArticleId><ArticleId IdType="pii">32/1/380</ArticleId><ArticleId IdType="pmc">PMC373290</ArticleId></ArticleIdList><ReferenceList><Reference><Citation>Mol Biol Evol. 1987 Jul;4(4):406-25</Citation><ArticleIdList><ArticleId IdType="pubmed">3447015</ArticleId></ArticleIdList></Reference><Reference><Citation>J Theor Biol. 1986 Mar 21;119(2):205-18</Citation><ArticleIdList><ArticleId IdType="pubmed">3461222</ArticleId></ArticleIdList></Reference><Reference><Citation>J Mol Biol. 1990 Oct 5;215(3):403-10</Citation><ArticleIdList><ArticleId IdType="pubmed">2231712</ArticleId></ArticleIdList></Reference><Reference><Citation>J Mol Biol. 1991 Jun 5;219(3):555-65</Citation><ArticleIdList><ArticleId IdType="pubmed">2051488</ArticleId></ArticleIdList></Reference><Reference><Citation>Comput Appl Biosci. 1992 Jun;8(3):275-82</Citation><ArticleIdList><ArticleId IdType="pubmed">1633570</ArticleId></ArticleIdList></Reference><Reference><Citation>Proc Natl Acad Sci U S A. 1992 Nov 15;89(22):10915-9</Citation><ArticleIdList><ArticleId IdType="pubmed">1438297</ArticleId></ArticleIdList></Reference><Reference><Citation>Nucleic Acids Res. 1994 Nov 11;22(22):4673-80</Citation><ArticleIdList><ArticleId IdType="pubmed">7984417</ArticleId></ArticleIdList></Reference><Reference><Citation>Proc Int Conf Intell Syst Mol Biol. 1996;4:230-40</Citation><ArticleIdList><ArticleId IdType="pubmed">8877523</ArticleId></ArticleIdList></Reference><Reference><Citation>Nucleic Acids Res. 1998 Jan 1;26(1):316-9</Citation><ArticleIdList><ArticleId IdType="pubmed">9399863</ArticleId></ArticleIdList></Reference><Reference><Citation>Proteins. 2000 Feb 1;38(2):149-64</Citation><ArticleIdList><ArticleId IdType="pubmed">10656262</ArticleId></ArticleIdList></Reference><Reference><Citation>Protein Eng. 2000 Mar;13(3):149-52</Citation><ArticleIdList><ArticleId IdType="pubmed">10775656</ArticleId></ArticleIdList></Reference><Reference><Citation>J Comput Biol. 2000 Feb-Apr;7(1-2):1-46</Citation><ArticleIdList><ArticleId IdType="pubmed">10890386</ArticleId></ArticleIdList></Reference><Reference><Citation>Mol Biol Evol. 2002 Jan;19(1):8-13</Citation><ArticleIdList><ArticleId IdType="pubmed">11752185</ArticleId></ArticleIdList></Reference><Reference><Citation>Nucleic Acids Res. 2002 Jul 15;30(14):3059-66</Citation><ArticleIdList><ArticleId IdType="pubmed">12136088</ArticleId></ArticleIdList></Reference><Reference><Citation>J Mol Biol. 2003 Feb 7;326(1):317-36</Citation><ArticleIdList><ArticleId IdType="pubmed">12547212</ArticleId></ArticleIdList></Reference><Reference><Citation>Bioinformatics. 2003 Mar 1;19(4):513-23</Citation><ArticleIdList><ArticleId IdType="pubmed">12611807</ArticleId></ArticleIdList></Reference><Reference><Citation>Protein Eng. 2003 May;16(5):323-30</Citation><ArticleIdList><ArticleId IdType="pubmed">12826723</ArticleId></ArticleIdList></Reference><Reference><Citation>Proc Natl Acad Sci U S A. 1988 Apr;85(8):2444-8</Citation><ArticleIdList><ArticleId IdType="pubmed">3162770</ArticleId></ArticleIdList></Reference></ReferenceList></PubmedData></pubmed></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/PubMed/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002411 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PubMed/Curation/biblio.hfd -nk 002411 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= PubMed
|étape= Curation
|type= RBID
|clé= pubmed:14729922
|texte= Local homology recognition and distance measures in linear time using compressed amino acid alphabets.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/PubMed/Curation/RBID.i -Sk "pubmed:14729922" \
| HfdSelect -Kh $EXPLOR_AREA/Data/PubMed/Curation/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |