Computing nearest neighbour interchange distances between ranked phylogenetic trees.

Area of Science:

• Computational Biology
• Phylogenetics
• Graph Theory

Background:

• Phylogenetic tree algorithms often rely on tree rearrangement operations, creating graphs where trees are vertices and rearrangements are edges.
• Computing distances in these graphs is computationally challenging, often NP-hard, hindering practical applications in fields like cancer research and epidemiology.
• The shortest path problem for ranked phylogenetic trees under common rearrangement operations remained unsolved for decades.

Purpose of the Study:

• To determine the computational complexity of the shortest path problem for ranked phylogenetic trees under the ranked nearest neighbor interchange (RNI) operation.
• To develop an efficient algorithm for computing distances between ranked phylogenetic trees using RNI.
• To provide the first example of a phylogenetic tree rearrangement operation where shortest paths can be computed efficiently.

Main Methods:

• Analysis of the computational complexity of the shortest path problem for ranked nearest neighbor interchange.
• Development of a novel algorithm for computing shortest paths and distances between ranked phylogenetic trees.
• Evaluation of the algorithm's scalability on large datasets.

Main Results:

• The computational complexity for ranked nearest neighbor interchange is established, dependent on the weight difference between rank and edge moves.
• Complexity varies from quadratic (efficient) to NP-hard (computationally intractable).
• The developed algorithm efficiently computes shortest paths and distances, scaling to trees with tens of thousands of leaves.

Conclusions:

• The shortest path problem for ranked phylogenetic trees under ranked nearest neighbor interchange is now computationally understood.
• This research provides the first efficient algorithm for computing distances using this specific rearrangement operation.
• The efficient algorithm has significant implications for phylogenetic inference and comparison in various biological applications.