SPARK-MSNA

SPARK-MSNA performs scalable multiple sequence alignment of similar DNA/RNA sequences using Apache Spark to support large-scale phylogenetic and comparative genomics analyses.

Key Features:

• Knowledge-driven alignment: Leverages sequence similarity features to improve alignment efficiency compared to traditional methods.
• Suffix trees: Incorporates suffix trees to identify common substrings and target regions for alignment.
• Modified Needleman-Wunsch: Uses a modified Needleman-Wunsch algorithm for pairwise alignments to enhance performance and accuracy.
• Supervised nearest-neighbor learning: Integrates supervised learning with a nearest neighbor algorithm and a knowledge base to reduce pairwise alignment complexity from O(m^2) to O(m).
• Improved resource utilization: Demonstrated approximately 50% memory improvement over HAlign II on human mitochondrial genome datasets while maintaining or improving accuracy.
• Apache Spark scalability: Implements the algorithm within the Apache Spark framework to enable execution on massive datasets with improved execution times.

Scientific Applications:

• Phylogenetic tree construction: Supports generation of alignments suitable for phylogenetic analyses.
• Comparative genomics: Facilitates large-scale comparative analyses of DNA/RNA sequences across genomes.
• Large-scale genomic datasets: Enables analysis of extensive datasets such as human mitochondrial genomes where memory and runtime are limiting factors.

Methodology:

Combines suffix trees, a modified Needleman-Wunsch pairwise alignment algorithm, and supervised nearest-neighbor learning guided by a knowledge base, implemented on Apache Spark (complexity reduction from O(m^2) to O(m) explicitly reported).