Journal Article

Local homology recognition and distance measures in linear time using compressed amino acid alphabets

Robert C. Edgar

in Nucleic Acids Research

Volume 32, issue 1, pages 380-385
Published in print January 2004 | ISSN: 0305-1048
Published online January 2004 | e-ISSN: 1362-4962 | DOI:
Local homology recognition and distance measures in linear time using compressed amino acid alphabets

More Like This

Show all results sharing this subject:

  • Bioinformatics and Computational Biology


Show Summary Details


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.

Journal Article.  4618 words.  Illustrated.

Subjects: Bioinformatics and Computational Biology

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.