Breaking the computational barriers of pairwise genome comparison

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Conventional pairwise sequence comparison algorithms struggle with large datasets, causing processing bottlenecks.
• Existing software limitations hinder the efficient computational analysis of massive biological sequence data.
• There is a significant challenge in overcoming these barriers for the bioinformatics community.

Purpose of the Study:

• To develop efficient C libraries for pairwise sequence comparison across diverse computing architectures.
• To address the limitations of current algorithms when processing large biological sequence datasets.
• To enable the analysis of datasets previously too large for conventional methods.

Main Methods:

• Developed modular C libraries for pairwise sequence comparison.
• Implemented an out-of-core strategy utilizing secondary storage to manage memory constraints.
• Applied software engineering principles to minimize I/O impact and avoid redundant calculations.

Main Results:

• Achieved linear-time response and controlled memory consumption for large sequence datasets.
• Demonstrated high-quality results comparable to or faster than state-of-the-art methods.
• Successfully tested across various architectures, from commodity systems to cloud environments.

Conclusions:

• Successfully addressed pairwise and all-versus-all comparison of large sequences, expanding input data size limits.
• The modular out-of-core strategy effectively manages memory during High-scoring Segment Pair (HSP) identification.
• The computationally efficient approach enhances flexibility and extendibility for tasks like whole-genome comparison and evolutionary analysis.