Polyploidy Arithmetic

Area of Science:

• Evolutionary Biology
• Genomics
• Computational Biology

Background:

• Polyploidy, the duplication of entire genomes, is a significant driver of speciation and genome evolution in plants and animals.
• Understanding the evolutionary history of polyploid species requires determining the minimum number of hybridization events that could explain observed ploidy levels.

Purpose of the Study:

• To rephrase the fundamental question of determining the minimum hybridizations for a given ploidy profile.
• To establish the computational complexity of this problem and explore its connections to mathematical concepts and network representations.

Main Methods:

• Rephrasing the hybridization number problem in terms of addition chains and addition sequences.
• Demonstrating the equivalence between finding the hybridization number and solving the addition sequence problem.
• Utilizing tree-child networks and beaded tree-child networks to model polyploid evolution.

Main Results:

• The problem of finding the minimum number of hybridizations (hybrid number) is equivalent to the computationally intractable addition sequence problem.
• Ploidy profiles representable by tree-child networks correspond exactly to addition chains, enabling polynomial-time identification algorithms.
• A greedy polynomial-time algorithm was developed to determine if a given ploidy profile can be realized by beaded tree-child networks, accounting for autopolyploidy.

Conclusions:

• The study establishes a formal link between polyploid evolution and the mathematical theory of addition sequences and chains.
• This connection implies the computational intractability of determining the minimum hybridization number for arbitrary ploidy profiles.
• New algorithmic approaches are presented for identifying specific types of polyploid evolutionary histories using network models, paving the way for future research in polyploid speciation and genome evolution.