Protein sequence-similarity search acceleration using a heuristic algorithm with a sensitive matrix

Kyungtaek Lim, Kazunori D. Yamada, Martin C. Frith, Kentaro Tomii

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Protein database search for public databases is a fundamental step in the target selection of proteins in structural and functional genomics and also for inferring protein structure, function, and evolution. Most database search methods employ amino acid substitution matrices to score amino acid pairs. The choice of substitution matrix strongly affects homology detection performance. We earlier proposed a substitution matrix named MIQS that was optimized for distant protein homology search. Herein we further evaluate MIQS in combination with LAST, a heuristic and fast database search tool with a tunable sensitivity parameter m, where larger m denotes higher sensitivity. Results show that MIQS substantially improves the homology detection and alignment quality performance of LAST across diverse m parameters. Against a protein database consisting of approximately 15 million sequences, LAST with m = 105 achieves better homology detection performance than BLASTP, and completes the search 20 times faster. Compared to the most sensitive existing methods being used today, CS-BLAST and SSEARCH, LAST with MIQS and m = 106 shows comparable homology detection performance at 2.0 and 3.9 times greater speed, respectively. Results demonstrate that MIQS-powered LAST is a time-efficient method for sensitive and accurate homology search.

Original languageEnglish
Pages (from-to)147-154
Number of pages8
JournalJournal of Structural and Functional Genomics
Issue number4
Publication statusPublished - 2016 Dec 1


  • Alignment quality
  • Amino acid substitution matrix
  • Homology detection


Dive into the research topics of 'Protein sequence-similarity search acceleration using a heuristic algorithm with a sensitive matrix'. Together they form a unique fingerprint.

Cite this