constNJ: an algorithm to reconstruct sets of phylogenetic trees satisfying pairwise topological constraints

Area of Science:

• Computational Biology
• Phylogenetics
• Evolutionary Biology

Background:

• Phylogenetic reconstruction aims to infer evolutionary relationships.
• Existing methods may struggle to produce trees compatible with complex evolutionary scenarios like networks.
• Fitting trees into networks post-reconstruction can be challenging.

Purpose of the Study:

• Introduce constNJ (constrained neighbor-joining), a novel algorithm for phylogenetic tree reconstruction.
• Address the challenge of constructing sets of trees that fit within evolutionary networks.
• Enforce specific rooted subtree-prune-regraft (rSPR) distance constraints during tree estimation.

Main Methods:

• ConstNJ algorithm utilizes distance matrices from sequence blocks.
• Incorporates rSPR distance constraint inequalities between pairs of trees.
• Employs maximum agreement partitions (MAPs) to ensure constraint satisfaction.

Main Results:

• ConstNJ provides a method for phylogenetic reconstruction with explicit network compatibility.
• The algorithm generalizes the neighbor-joining method.
• Ensures resulting trees satisfy user-defined rSPR distance constraints.

Conclusions:

• ConstNJ offers a robust approach to inferring phylogenetic trees compatible with evolutionary networks.
• This method is particularly useful for analyzing data with potential recombination or hybridization.
• The use of MAPs guarantees adherence to specified phylogenetic distance constraints.