Parallel implementation of D-Phylo algorithm for maximum likelihood clusters.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Phylogenetic analysis is crucial for understanding evolutionary relationships.
• Existing algorithms, like those using k-means, face limitations such as getting stuck at conserved motifs.
• Efficient parallel algorithms are needed for analyzing large DNA sequence datasets.

Purpose of the Study:

• To introduce and evaluate D-Phylo, a novel parallel algorithm for DNA phylogenetic analysis.
• To demonstrate D-Phylo's improved performance and accuracy compared to traditional methods.
• To leverage the maximum likelihood approach for enhanced phylogenetic inference.

Main Methods:

• Development of the D-Phylo parallel algorithm.
• Utilizing a modified k-means approach to avoid local optima.
• Testing on real-life DNA datasets using high-performance computing resources (Amazon Linux, 6 CPU, 122 GiB RAM, 15 processors).

Main Results:

• D-Phylo effectively performs phylogenetic analysis using the maximum likelihood method.
• The algorithm avoids the constraint of getting stuck at privately conserved motifs, a limitation of standard k-means.
• Near-linear speedup was achieved with an even distribution of clusters across multiple processors.

Conclusions:

• D-Phylo represents an advancement in parallel phylogenetic analysis of DNA sequences.
• The algorithm offers a robust and efficient solution for large-scale evolutionary studies.
• Its performance on high-performance computing infrastructure highlights its scalability.