SPARK-MSNA: Efficient algorithm on Apache Spark for aligning multiple similar DNA/RNA sequences with supervised...

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Multiple sequence alignment (MSA) is crucial for molecular biology but struggles with large datasets.
• Existing tools face bottlenecks when handling massive numbers of long sequences.
• Knowledge-driven approaches leveraging sequence similarity can enhance DNA MSA efficiency.

Purpose of the Study:

• To demonstrate the advantages of using similarity features in DNA sequence alignment.
• To develop a more efficient and scalable MSA algorithm for large biological datasets.
• To improve memory utilization and alignment accuracy in large-scale genomic analyses.

Main Methods:

• Utilizes suffix trees to identify common substrings within sequences.
• Employs a modified Needleman-Wunsch algorithm for pairwise alignments.
• Integrates a knowledge base and a supervised nearest neighbor algorithm to guide alignments.
• Implements the algorithm on the Apache Spark big data framework for scalability.

Main Results:

• Achieves linear time complexity O(m), a significant improvement over O(m^2).
• SPARK-MSNA demonstrates 50% better memory utilization for human mitochondrial genomes compared to state-of-the-art methods.
• Provides improved alignment accuracy (average SP score) with comparable execution times.
• Scalable implementation on Apache Spark handles large datasets effectively.

Conclusions:

• Knowledge-driven algorithms, like SPARK-MSNA, offer substantial improvements in DNA MSA efficiency and accuracy.
• The SPARK-MSNA algorithm is a scalable solution for handling large-scale genomic data.
• This approach aids critical downstream applications such as phylogenetic tree construction and comparative genomics.