OrientAGraph

OrientAGraph integrates Maximum Likelihood Network Orientation into TreeMix to estimate admixture graphs that model population evolutionary histories involving interbreeding.

Key Features:

• Admixture Graph Modeling: Admixture graphs extend phylogenetic trees by incorporating nodes that represent admixture events between distinct populations.
• Inferential Challenges: The space of possible admixture graphs is large, requiring accurate and computationally efficient search heuristics; TreeMix optimizes a likelihood objective by iteratively adding edges to a starting tree.
• Local Optima Issue: Starting-tree-based maximum likelihood heuristics such as TreeMix can become trapped in local optima, producing incorrect network topologies, particularly when an admixed population is incident to a leaf.
• Maximum Likelihood Network Orientation (MLNO): OrientAGraph implements MLNO as a search strategy that conducts exhaustive searches over network orientations to improve likelihood estimation and topological accuracy.
• Performance Evaluation: Comparative evaluations on previously published admixture graphs showed OrientAGraph identified higher-likelihood and more topologically accurate graphs than TreeMix in four of eight tested models while not compromising computational efficiency.

Scientific Applications:

• Population genetics: Estimating admixture graphs to resolve population structure and historical admixture events.
• Evolutionary biology: Reconstructing complex demographic histories, including aspects of human evolution and other species' evolutionary dynamics.
• Demographic inference: Inferring demographic models of populations shaped by interbreeding using likelihood-based network approaches.

Methodology:

Integrates Maximum Likelihood Network Orientation (MLNO) as a search heuristic within TreeMix, performs exhaustive searches over network orientations, and relies on maximum likelihood optimization via iterative edge additions to a starting tree.