An efficient parallel algorithm for multiple sequence similarities calculation using a low complexity method

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Genomic research generates vast amounts of sequence data, necessitating efficient comparative methods.
• Calculating sequence similarities is crucial for numerous bioinformatics applications.
• Handling large datasets requires combining low-complexity methods with parallel computing.

Purpose of the Study:

• To develop a parallel algorithm for calculating multiple sequence similarities using k-mers counting.
• To address the computational challenges posed by the increasing volume of genomic data.

Main Methods:

• Implementation of a parallel algorithm based on the k-mers counting method.
• Utilizing parallel computing to enhance the efficiency of similarity calculations.
• Testing the algorithm's performance and scalability.

Main Results:

• The developed parallel algorithm demonstrates very good scalability.
• A nearly linear speedup was achieved, with a 12x speedup observed for 14 nodes.
• The k-mers counting method provides efficient and biologically relevant results.

Conclusions:

• The proposed parallel algorithm offers a significant improvement for multiple sequence similarity calculations.
• This approach can be integrated into parallel versions of popular multiple sequence alignment tools like MAFFT and MUSCLE.
• Efficient handling of large genomic datasets is achievable through parallel computing and optimized algorithms.