Reconciling multiple genes trees via segmental duplications and losses

Area of Science:

• Computational Biology
• Evolutionary Biology
• Bioinformatics

Background:

• Understanding gene family evolution is crucial for evolutionary studies.
• Existing methods often reconcile gene trees independently, neglecting interconnectedness.
• Segmental macro-evolutionary events (duplications and losses) play a key role.

Purpose of the Study:

• To extend existing approaches for reconciling multiple gene trees with a species tree.
• To analyze the computational complexity of gene tree reconciliation under segmental macro-evolutionary events.
• To develop an efficient algorithm for gene tree reconciliation with a focus on segmental duplications.

Main Methods:

• Developed a novel approach for reconciling a set of gene trees with a species tree.
• Analyzed the problem's complexity, identifying polynomial-time solvability for specific cost parameters and NP-hardness for others.
• Designed a fixed-parameter algorithm with complexity dependent on duplication cost and number of segmental duplications.

Main Results:

• Demonstrated polynomial-time solvability for gene tree reconciliation when duplication cost equals loss cost.
• Proved the problem is NP-hard when duplication cost is less than loss cost, even for a single gene tree.
• Developed a fixed-parameter tractable algorithm with time complexity dependent on duplication cost and the number of segmental duplications.
• Applied the algorithm to real datasets, confirming hypothetical segmental duplications in eukaryotes and detecting whole genome duplications in yeast.

Conclusions:

• The study provides a comprehensive analysis of gene tree reconciliation complexity.
• The developed fixed-parameter algorithm offers an efficient solution for complex evolutionary scenarios.
• The method's application to real datasets highlights its utility in evolutionary and genomic studies.