GraphDTL

GraphDTL constructs a minimum reconciliation graph using a polynomial-space and polynomial-time algorithm to represent all most parsimonious reconciliations between gene trees and species trees for comparative genomic analysis of evolutionary events.

Key Features:

• Polynomial-space and polynomial-time algorithm: Efficiently constructs the minimum reconciliation graph summarizing optimal reconciliations without enumerating an exponential number of solutions.
• Comprehensive scenario representation: Encodes all most parsimonious reconciliations between gene trees and species trees to expose alternative evolutionary narratives under parsimony criteria.
• Counting non-equivalent solutions: Enables counting and comparison of non-equivalent most parsimonious reconciliations to quantify ambiguity among optimal scenarios.

Scientific Applications:

• Comparative genomics reconciliation: Summarizes all optimal reconciliations to support interpretation of gene tree versus species tree conflicts in comparative genomic studies.
• Evolutionary scenario exploration: Facilitates exploration and comparison of alternative evolutionary histories implied by most parsimonious reconciliations.
• Parsimony robustness assessment: Assesses the robustness and ambiguity of parsimony-based inferences by identifying and counting multiple equivalent reconciliation solutions.

Methodology:

A polynomial-space and polynomial-time algorithm constructs a minimum reconciliation graph that encodes all most parsimonious reconciliations between input gene trees and species trees.