Related Experiment Videos
Reconstruction of large phylogenetic trees: a parallel approach
Zhihua Du1, Feng Lin, Usman W Roshan
1BioInformatics Research Centre, Nanyang Technological University, Nanyang Avenue, Singapore 639798, Singapore. duzhihua@pmail.ntu.edu.sg
Computational Biology and Chemistry
|July 26, 2005
Summary
This study introduces a parallel computing model for reconstructing large phylogenetic trees, significantly reducing computation time on Multiple Instruction Multiple Data (MIMD) systems. The new method achieves faster results than sequential approaches, making complex phylogenetic analysis more accessible.
Area of Science:
- Computational Biology
- Bioinformatics
- Computer Science
Background:
- Phylogenetic tree reconstruction for large datasets is computationally intensive.
- Existing methods face challenges with scalability and processing time.
Purpose of the Study:
- To present a parallel computing model for phylogenetic tree reconstruction on Multiple Instruction Multiple Data (MIMD) architectures.
- To adapt the recursive-DCM3 decomposition method for efficient parallel processing.
Main Methods:
- A divide-and-conquer strategy is employed, breaking down large datasets into smaller subproblems.
- Computation load is distributed across multiple processors for parallel subtree construction.
- Subtrees are merged into a final supertree using a flexible approach.
Main Results:
- The parallel model significantly reduces computational time compared to sequential versions.
- A case study demonstrated a 22.1-hour runtime on four processors, outperforming a previous 123.7-hour record.
- The program is developed using the Message Passing Interface (MPI) for broad compatibility.
Conclusions:
- The proposed parallel computing model offers a flexible and efficient solution for large-scale phylogenetic tree reconstruction.
- This approach enhances the feasibility of analyzing very large biological datasets.
- The model's performance improvements pave the way for more extensive phylogenetic studies.