An efficient exact algorithm for computing all pairwise distances between reconciliations in the...

Area of Science:

• Computational Biology
• Evolutionary Biology
• Bioinformatics

Background:

• Maximum parsimony reconciliation is vital for analyzing evolutionary histories of genes, species, parasites, and symbionts.
• Existing algorithms efficiently find reconciliations, but the sheer number can be exponential, necessitating an understanding of the reconciliation space.
• Determining if a single reconciliation suffices or if multiple are needed requires deeper insight into this space.

Purpose of the Study:

• To develop an efficient algorithm for computing the distribution of pairwise distances in maximum parsimony reconciliation.
• To provide a method for characterizing the space of maximum parsimony reconciliations.
• To offer new insights into the structure of reconciliation spaces.

Main Methods:

• Developed and described an efficient polynomial-time algorithm.
• The algorithm computes the exact distribution of pairwise distances for any reconciliation problem instance.
• Analyzed the algorithm's asymptotic worst-case running time.

Main Results:

• An efficient polynomial-time algorithm was developed to compute the distribution of pairwise distances.
• The algorithm is exact for multiple distance metrics.
• Demonstrated the algorithm's utility and viability on a large biological dataset.

Conclusions:

• The study provides novel insights into the structure of the space of maximum parsimony reconciliations.
• These findings are valuable for various applications utilizing reconciliation methods in evolutionary and coevolutionary studies.