On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem

Christian Komusiewicz, Simone Linz, Nils Morawietz, Jannik SchestagCPM 2023 · DOI

TL;DR

This paper investigates the computational complexity of finding a better phylogenetic tree within a limited "neighborhood" of an existing tree, a common heuristic for the notoriously hard Maximum Parsimony problem. They prove that for most common tree distance measures, searching these neighborhoods is inherently difficult, suggesting that current brute-force approaches are nearly optimal. However, they identify a specific distance measure (k-sECR) where more efficient search is possible.

What Problem Does This Paper Address?

The Maximum Parsimony (MP) problem is a fundamental task in bioinformatics, aiming to reconstruct the evolutionary history of a set of species (taxa) by finding the phylogenetic tree that requires the fewest evolutionary changes (mutations). This problem is computationally very challenging, even for simple cases. To tackle this, researchers often employ "local search" heuristics. These heuristics start with an initial tree and iteratively search for a "neighboring" tree with a better parsimony score. The "neighborhood" is defined by a distance metric, representing how many operations (like rearranging subtrees) are needed to transform one tree into another.

A key question is: how hard is it to find a better tree within a k-neighborhood? That is, can we efficiently find a tree that is at most k operations away from our current tree and has a lower parsimony score? This paper focuses on the parameterized complexity of this question, where the difficulty is analyzed with respect to the parameter k. They investigate several standard tree distance measures (NNI, SPR, TBR, ECR) and a more restricted version (sECR).

Methods

The authors use the framework of parameterized complexity to analyze the hardness of searching k-neighborhoods. This involves:

  • W[1]-hardness: A complexity class indicating that a problem is likely hard to solve efficiently even when a parameter (like k) is small.
  • Exponential Time Hypothesis (ETH): A conjecture that certain problems cannot be solved faster than exponential time in their input size. The authors use this to establish lower bounds on running times.
  • Reductions: They prove hardness results by reducing known hard problems (like CLIQUE) to their problem. This means if their problem could be solved efficiently, the known hard problem could also be solved efficiently, which is believed to be impossible.
  • Algorithm Design: For the k-sECR distance, they develop an algorithm that is more efficient than brute-force.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and algorithm design, not empirical evaluation on biological datasets.

Key Insights and Ideas

  • The "Curse of the Neighborhood" for Most Distances: For common tree distance measures like NNI, SPR, and TBR, searching a k-neighborhood is fundamentally hard. This implies that simply increasing the "search radius" k doesn't offer a significant algorithmic speedup over brute-force, even with advanced parameterized complexity techniques.
  • The k-sECR Exception: The k-sECR distance, which restricts the contracted edges to form a subtree, offers a surprising algorithmic advantage. This suggests that specific structural constraints on the neighborhood definition can lead to more tractable problems.
  • Tight Bounds: The paper establishes tight upper and lower bounds for the running time of searching these neighborhoods, meaning their algorithms are essentially as fast as theoretically possible given current complexity assumptions.
  • Connection to CLIQUE: The hardness proofs cleverly use reductions from the CLIQUE problem, highlighting a deep connection between finding dense subgraphs and searching for better phylogenetic trees within specific neighborhood structures.

Key Results

  • Hardness for NNI, SPR, TBR, and ECR: For these distances, the problem of finding a better tree in a k-neighborhood is proven to be W[1]-hard with respect to k. Under the ETH, no algorithm can run faster than $|I|^{o(k)}$ (where $|I|$ is input size), meaning brute-force is essentially optimal.
  • Efficient Algorithm for k-sECR: For the k-sECR distance, an algorithm with running time $k^{o(k)} \cdot |I|^{O(1)}$ is presented, which is significantly faster for larger k.
  • Tight Running Times: The paper provides tight bounds for the running times of algorithms for NNI, SPR, TBR, and k-ECR, showing they are $n^{\Theta(k)} \cdot m^{O(1)}$ or similar, matching the lower bounds.

Limitations and Future Work

  • k-sECR Bottleneck: The authors note that improving the running time for the k-sECR neighborhood is a key area for future research, as the current bottleneck lies in enumerating tree refinements.
  • Perfect Phylogeny: The paper focuses on finding better trees. An open question is whether better running times are possible when searching for a perfect phylogeny (a tree where each character requires only one mutation).
  • Other Neighborhoods: The paper poses the question of whether other neighborhood definitions could lead to more efficient algorithms.

Summary updated

BibTeX
@inproceedings{komusiewicz2023complexity,
  author = {Christian Komusiewicz and Simone Linz and Nils Morawietz and Jannik Schestag},
  title = {{On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem}},
  booktitle = {CPM},
  year = {2023},
  doi = {10.4230/lipics.cpm.2023.18},
}
Figure