Computational complexity of inferring phylogenies from chromosome inversion data

Area of Science:

• Systematics
• Evolutionary Biology
• Computational Biology

Background:

• Parsimony methods are widely used in systematics to construct phylogenetic trees by minimizing evolutionary change.
• Chromosome inversions present unique challenges in phylogenetic inference due to homozygous and heterozygous states.
• Existing parsimony criteria for chromosome inversions vary based on ancestral state specification.

Purpose of the Study:

• To analyze the computational complexity of phylogenetic inference using parsimony criteria for chromosome inversions.
• To determine if efficient algorithms exist for inferring phylogenies under these specific parsimony criteria.

Main Methods:

• Investigated parsimony methods applied to chromosome inversion polymorphisms.
• Analyzed variations of the parsimony criterion concerning ancestral states.
• Utilized computational complexity theory to assess problem tractability.

Main Results:

• Established that phylogenetic inference problems using chromosome inversion parsimony criteria are NP-complete.
• Demonstrated that these problems are computationally intractable.
• Showed that efficient optimal algorithms for these problems are unlikely to exist.

Conclusions:

• Phylogenetic inference using parsimony for chromosome inversions is computationally demanding.
• The NP-complete nature of these problems implies significant challenges for finding optimal solutions efficiently.
• Future research may need to explore heuristic or approximate methods for phylogenetic reconstruction in such cases.