An Algorithm for Calculating the Probability of Classes of Data Patterns on a Genealogy

Area of Science:

• Computational Biology
• Phylogenetics
• Evolutionary Modeling

Background:

• Felsenstein's pruning algorithm calculates data pattern probabilities on phylogenies.
• Existing methods face limitations with large datasets and complex evolutionary models.

Purpose of the Study:

• Introduce a novel dynamic programming algorithm for phylogenetic pattern probability calculation.
• Expand the feasibility of analyzing large datasets in phylogenetic model assessment.
• Enable efficient likelihood calculations correcting for ascertainment biases.

Main Methods:

• Developed a dynamic programming algorithm treating the phylogenetic tree and evolutionary model as known.
• Algorithm bins character patterns by parsimony steps and observed tip states.
• Implemented the algorithm in open-source C++ software.

Main Results:

• The algorithm efficiently calculates probabilities for various character pattern classes.
• It proves more efficient than enumeration for parsimony-uninformative patterns in complex models.
• Enables analysis of larger datasets and more intricate evolutionary scenarios.

Conclusions:

• The new algorithm enhances the scalability and efficiency of phylogenetic analyses.
• It supports advanced model testing and likelihood calculations with ascertainment bias correction.
• Facilitates broader application of phylogenetic methods in evolutionary biology research.