PhyML

PhyML implements fast heuristic algorithms for estimating maximum likelihood phylogenies from DNA and protein sequences.

Key Features:

• Maximum likelihood tree estimation: Simultaneously adjusts tree topology and branch lengths using a hill-climbing algorithm to optimize the likelihood function.
• Nearest neighbor interchanges (NNI): Performs fast topological rearrangements to improve a starting tree topology.
• Subtree pruning and regrafting (SPR): Searches tree space with user-defined intensity using SPR moves, with parsimony-based filtering to discard unpromising topology modifications.
• Approximate likelihood-ratio test (aLRT): Provides fast branch support assessment using a test statistic of 2(l1-l2), the difference between the maximum log-likelihood of the best tree and the second best topological arrangement around the branch of interest.
• Shimodaira-Hasegawa-like branch test: Extends the aLRT with a nonparametric procedure to assess support for internal branches.
• Nonparametric bootstrap: Supports bootstrap analysis for comprehensive phylogenetic inference.
• Evolutionary parameter estimation: Estimates various evolutionary parameters as part of phylogenetic analysis.
• SPR efficiency improvements: Uses distance-based filtering to detect and discard unpromising candidate SPR moves, and locally estimates likelihood changes rather than globally evaluating the entire tree for each move.

Scientific Applications:

• Phylogenetic reconstruction: Estimates evolutionary relationships from DNA and protein sequence alignments using maximum likelihood.
• Large dataset analysis: Processes large nucleotide and amino acid datasets, including multi-gene datasets with conflicting signals, in reasonable computing time.
• Branch support assessment: Evaluates statistical support for internal branches using aLRT, extended likelihood-ratio tests, or nonparametric bootstrap.
• Plant phylogenetics: Has been applied to large plant plastid datasets such as 500 rbcL sequences with 1,428 base pairs.

Methodology:

PhyML starts from an initial tree built by a fast distance-based method, then modifies this tree through simultaneous adjustment of topology and branch lengths to improve likelihood at each iteration. For SPR moves, the algorithm uses a two-step filtering strategy: first applying a fast distance-based approach to discard unpromising candidate SPR moves, then locally estimating the change in likelihood for remaining potential SPRs by optimizing only over the branch of interest and four adjacent branches while fixing other parameters at their optimal values.