Convex recolorings of strings and trees: Definitions, hardness results and algorithms

https://doi.org/10.1016/j.jcss.2007.10.003Get rights and content
Under an Elsevier user license
open archive

Abstract

A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex colorings of trees arise in areas such as phylogenetics, linguistics, etc., e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree.

When a coloring of a tree is not convex, it is desirable to know “how far” it is from a convex one, and what are the convex colorings which are “closest” to it. In this paper we study a natural definition of this distance—the recoloring distance, which is the minimal number of color changes at the vertices needed to make the coloring convex. We show that finding this distance is NP-hard even for a colored string (a path), and for some other interesting variants of the problem. In the positive side, we present algorithms for computing the recoloring distance under some natural generalizations of this concept: the first generalization is the uniform weighted model, where each vertex has a weight which is the cost of changing its color. The other is the non-uniform model, in which the cost of coloring a vertex v by a color d is an arbitrary non-negative number cost(v,d). Our first algorithms find optimal convex recolorings of strings and bounded degree trees under the non-uniform model in time which, for any fixed number of colors, is linear in the input size. Next we improve these algorithm for the uniform model to run in time which is linear in the input size for a fixed number of bad colors, which are colors which violate convexity in some natural sense. Finally, we generalize the above result to hold for trees of unbounded degree.

Keywords

Algorithms
Complexity
Phylogenetics
Dynamic programming
Fixed parameter tractability

Cited by (0)

A preliminary version of some of the results in this paper appeared in [S. Moran, S. Snir, Convex recoloring of strings and trees, Technical Report CS-2003-13, Technion, November 2003. [17]].

1

This research was supported by the Technion VPR-fund and by the Bernard Elkin Chair in Computer Science.