title: Protein sequence-similarity search acceleration using a heuristic algorithm with a sensitive matrix.
abstract: 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 = 105achieves 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 = 106shows 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.
authors.affiliation: Artificial Intelligence Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-4-7 Aomi, Koto-ku, Tokyo, 135-0064, Japan.
authors.forename: Kyungtaek
authors.initials: K
authors.lastname: Lim
authors.affiliation: Artificial Intelligence Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-4-7 Aomi, Koto-ku, Tokyo, 135-0064, Japan.|Graduate School of Information Sciences, Tohoku University, 6-3-9 Aramaki-Aza-Aoba, Aoba-ku, Sendai, 980-8579, Japan.
authors.forename: Kazunori D
authors.initials: KD
authors.lastname: Yamada
authors.affiliation: Artificial Intelligence Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-4-7 Aomi, Koto-ku, Tokyo, 135-0064, Japan.|Department of Computational Biology and Medical Sciences, University of Tokyo, 5-1-5 Kashiwa-no-ha, Kashiwa, Chiba, 227-8561, Japan.
authors.forename: Martin C
authors.initials: MC
authors.lastname: Frith
authors.affiliation: Artificial Intelligence Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-4-7 Aomi, Koto-ku, Tokyo, 135-0064, Japan. k-tomii@aist.go.jp.|Biotechnology Research Institute for Drug Discovery, National Institute of Advanced Industrial Science and Technology (AIST), 2-4-7 Aomi, Koto-ku, Tokyo, 135-0064, Japan. k-tomii@aist.go.jp.
authors.forename: Kentaro
authors.initials: K
authors.lastname: Tomii
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D000067508:Computer Heuristics; D030562:Databases, Protein; D008958:Models, Molecular; D011506:Proteins / Q000737:chemistry; D016415:Sequence Alignment; D020539:Sequence Analysis, Protein
chemical_list: D011506:Proteins
keywords: Alignment quality; Amino acid substitution matrix; Homology detection