iARG

iARG reconstructs optimal ancestral recombination graphs by jointly modeling recombination and homoplasy to infer evolutionary histories.

Key Features:

• Unifying Model: Integrates recombination and homoplasy (back/recurrent mutations) into a single inferential model for evolutionary reconstruction.
• Optimal Ancestral Recombination Graph (ARG): Constructs optimal ancestral recombination graphs to represent detailed evolutionary histories.
• Algorithmic Innovation: Maps the reconstruction problem to the Directed Steiner Arborescence Problem from combinatorial optimization to enable algorithmic solutions.
• Linear Programming Techniques: Uses linear programming formulations to solve the Directed Steiner Arborescence Problem.
• Heuristic Methods: Employs heuristic approaches alongside exact algorithms to scale analysis to larger datasets.

Scientific Applications:

• Reconstruction of Evolutionary Histories: Infers evolutionary processes and genetic diversity by accounting for recombination and homoplasy.
• Analysis of Simulated Data Sets: Evaluates method performance on simulated data sets representing controlled evolutionary scenarios.
• Real Data Set Application: Applied to real data sets to analyze empirical genetic variation and evolutionary relationships.

Methodology:

Frames ARG reconstruction as a Directed Steiner Arborescence Problem and applies linear programming formulations and heuristic algorithms to compute optimal ancestral recombination graphs while modeling recombination and homoplasy.