Speeding up all-against-all protein comparisons while maintaining sensitivity by considering subsequence-level...

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• All-against-all (AAA) sequence comparisons are fundamental for orthology inference and multi-genome analyses.
• The quadratic scaling of AAA analyses presents a significant computational bottleneck, limiting the number of genomes that can be processed.
• Current methods struggle to balance speed and sensitivity in large-scale homology searches.

Purpose of the Study:

• To develop a significantly faster yet sensitive method for all-against-all sequence comparisons.
• To overcome the computational limitations of traditional AAA methods in genomic analyses.
• To improve the efficiency of orthology inference and related sequence analyses.

Main Methods:

• Exploited the transitivity of homology for computational efficiency.
• Ensured homology is defined using consistent protein subsequences.
• Developed a proof-of-concept implementation integrated into OMA standalone software.

Main Results:

• Achieved a 4x speedup in all-against-all sequence comparisons compared to standard methods.
• Recovered over 99.6% of homologous pairs identified by the full AAA procedure.
• Demonstrated superior recall compared to state-of-the-art k-mer approaches, which recover only 3-14% of homologous pairs.

Conclusions:

• The novel approach offers a substantial speed improvement for large-scale genomic analyses without compromising homology detection sensitivity.
• This method effectively addresses the computational bottleneck in all-against-all comparisons, enabling the analysis of more genomes.
• The open-source implementation facilitates broader adoption and further development in bioinformatics research.