Related Experiment Videos
Representation in stochastic search for phylogenetic tree reconstruction
Griffin Weber1, Lucila Ohno-Machado, Stuart Shieber
1Decision Systems Group, Brigham and Women's Hospital, Division of Health Sciences and Technology, Harvard and MIT, USA. weber@fas.harvard.edu
Journal of Biomedical Informatics
|December 20, 2005
Summary
This study introduces a novel stochastic search algorithm for phylogenetic tree reconstruction. The new method improves tree-building efficiency by using a different representation of evolutionary relationships, potentially yielding better results faster.
Area of Science:
- Computational Biology
- Evolutionary Biology
- Bioinformatics
Background:
- Phylogenetic tree reconstruction infers evolutionary relationships from DNA sequences.
- Finding the optimal phylogenetic tree is computationally intractable for large datasets.
- Popular heuristic methods like PAUP* use branch-swapping for stochastic tree searches.
Purpose of the Study:
- To introduce a new stochastic search algorithm for phylogenetic tree reconstruction.
- To explore an alternative representation of trees based on taxon processing order.
- To enhance the efficiency and accuracy of phylogenetic tree generation.
Main Methods:
- Developed a new stochastic search algorithm operating on tree permutations.
- Utilized stepwise addition order as an alternative tree representation.
- Evaluated the algorithm's performance on various biological datasets.
Main Results:
- The new algorithm, when used for initial tree generation followed by branch-swapping, produced superior trees.
- Improved tree quality was observed within a given computational time.
- The alternative tree representation facilitated a more effective search.
Conclusions:
- The proposed stochastic search algorithm offers a promising alternative for phylogenetic tree reconstruction.
- This approach can lead to more accurate evolutionary inferences.
- The findings suggest potential improvements for existing phylogenetic software.