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

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Protein database searching is crucial for structural and functional genomics.
• Amino acid substitution matrices significantly impact homology detection accuracy.
• Previous work introduced the MIQS matrix for distant protein homology search.

Purpose of the Study:

• To evaluate the MIQS substitution matrix combined with the LAST sequence alignment tool.
• To assess the performance of MIQS-LAST across various sensitivity parameters.
• To compare MIQS-LAST against existing homology search methods.

Main Methods:

• Utilized the MIQS substitution matrix with the LAST heuristic search tool.
• Tested LAST with a tunable sensitivity parameter (m) on a large protein database (approx. 15 million sequences).
• Compared performance against BLASTP, CS-BLAST, and SSEARCH.

Main Results:

• MIQS significantly improved LAST's homology detection and alignment quality.
• LAST with m=10^5 outperformed BLASTP and was 20x faster.
• LAST with MIQS and m=10^6 showed comparable sensitivity to CS-BLAST and SSEARCH at higher speeds.

Conclusions:

• MIQS-powered LAST provides a time-efficient method for sensitive and accurate protein homology searching.
• This approach enhances target selection in structural and functional genomics.
• The findings support the utility of MIQS for improving protein sequence analysis.