Finding Most Compatible Phylogenetic Trees over Multi-State Characters

Tuukka Korhonen, Matti JärvisaloAAAI 2020 · DOI

Introduction

In the field of phylogenetics, reconstructing the evolutionary history of species often involves building a "perfect phylogeny." This is an evolutionary tree where every biological trait, or character, evolves exactly once. For instance, a trait like "having feathers" should ideally appear on only a single branch of the tree. However, real-world biological data is frequently "imperfect" due to mutations, parallel evolution, or sequencing errors. When a perfect tree cannot be constructed for an entire dataset, researchers pivot to the Maximum Compatibility Problem (MCP): identifying the largest possible subset of characters that can be integrated into a perfect phylogeny.

While MCP is relatively straightforward for binary traits (e.g., presence or absence), it becomes NP-hard when applied to multi-state characters, such as the four bases of DNA or the twenty amino acids in proteins. Previous algorithmic frameworks have struggled to scale with the multi-state data essential for modern biological research.

Multi-state character data (left), its representation in a perfect phylogeny (middle), and the corresponding character-state conflict graph (right).

Methodology: A Hybrid BT-MaxSAT Approach

To overcome the computational bottlenecks of multi-state MCP, this research introduces a hybrid algorithm that bridges graph theory with declarative optimization. The approach combines two distinct paradigms:

  1. The Bouchitté-Todinca (BT) Framework: A classic graph-theoretic method used for triangulating graphs by identifying Potential Maximal Cliques (PMCs)—small, highly connected clusters of data. This framework provides a recursive structure for the search space.
  2. Maximum Satisfiability (MaxSAT): An optimization paradigm that balances "hard" constraints (mandatory rules) with "soft" constraints (optimization goals).

The Innovation

The core challenge in multi-state problems is that character incompatibility cannot always be determined locally within a recursive step; a character might be "broken" across distant parts of the tree. The authors addressed this by using the BT framework to define the structural constraints of the search space and then employing a MaxSAT solver to perform a global optimization. This allows the solver to "see" the entire problem at once, effectively bypassing the local-global barrier that hindered previous dynamic programming methods.

Graph-theoretic decomposition using the Bouchitté-Todinca framework to identify potential maximal cliques.

Key Insights and Results

The researchers evaluated their hybrid model against synthetic benchmarks and real-world datasets, including Chinese dialects, Indo-European languages, and mammal mitochondrial sequences.

  • Superior Scalability: The MaxSAT hybrid significantly outperformed existing state-of-the-art methods, such as Integer Programming and Pseudo-Boolean Optimization, particularly as the number of character states ($k$) increased.
  • Efficiency: While the initial graph analysis (PMC enumeration) remains a bottleneck, the MaxSAT solving phase was remarkably fast, averaging only 51 seconds on solved instances. Most real-world benchmarks were resolved in under 5 seconds.
  • Declarative Flexibility: By utilizing MaxSAT, the algorithm can handle missing data and weighted characters without requiring fundamental changes to the core logic.

Conclusion

By combining the structural strengths of the BT framework with the global optimization power of MaxSAT, this new approach provides a robust solution for reconstructing evolutionary trees from complex multi-state data. Future work will focus on optimizing the PMC enumeration phase to further enhance the speed of the initial graph analysis, potentially opening the door for even larger-scale phylogenetic studies.

Summary updated

BibTeX
@inproceedings{korhonen2020finding,
  author = {Tuukka Korhonen and Matti Järvisalo},
  title = {{Finding Most Compatible Phylogenetic Trees over Multi-State Characters}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5514},
}

Loading related content...

Figure