On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems

The aim of this paper is to give a complete picture of approximability for two tree consensus problems which are of particular interest in computational biology: Maximum Agreement SubTree (MAST) and Maximum Compatible Tree (MCT). Both problems take as input a label set and a collection of trees whose leaf sets are each bijectively labeled with the label set. Define the size of a tree as the number of its leaves. The well-known MAST problem consists of finding a maximum-sized tree that is topologically embedded in each input tree, under label-preserving embeddings. Its variant MCT is less stringent, as it allows the input trees to be arbitrarily refined. Our results are as follows. We show that MCT is -hard to approximate within bound n^1−? on rooted trees, where n denotes the size of each input tree; the same approximation lower bound was already known for MAST [J. Jansson, Consensus algorithms for trees and strings, Ph. D. Thesis, Lund University, 2003]. Furthermore, we prove that MCT on two rooted trees is not approximable within bound 2^log1−?n, unless all problems in are solvable in quasi-polynomial time; the same result was previously established for MAST on three rooted trees [J. Hein, T. Jiang, L. Wang, K. Zhang, On the complexity of comparing evolutionary trees, Discrete Applied Mathematics 71 (1-3) (1996) 153-169] (note that MAST on two trees is solvable in polynomial time [M.A. Steel, T.J. Warnow, Kaikoura tree theorems: Computing the maximum agreement subtree, Information Processing Letters 48 (2) (1993) 77-82]). Let CMAST, resp. CMCT, denote the complement version of MAST, resp. MCT: CMAST, resp. CMCT, consists of finding a tree that is a feasible solution of MAST, resp. MCT, and whose leaf label set excludes a smallest subset of the input labels. The approximation threshold for CMAST, resp. CMCT, on rooted trees is shown to be the same as the approximation threshold for CMAST, resp. CMCT, on unrooted trees; it was already known that both CMAST and CMCT are approximable within ratio three on rooted and unrooted trees [V. Berry, F. Nicolas, Maximum agreement and compatible supertrees, in: S.C. Sahinalp, S. Muthukrishnan, U. Dogrusoz (Eds.), Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM’04, in: LNCS, vol. 3109, Springer-Verlag, 2004, pp. 205-219; G. Ganapathy, T.J. Warnow, Approximating the complement of the maximum compatible subset of leaves of k trees, in: K. Jansen, S. Leonardi, V. V. Vazirani (Eds.), Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX’02, in: LNCS, vol. 2462, Springer-Verlag, 2002, pp. 122-134]. The latter results are completed by showing that CMAST is -hard on three rooted trees and that CMCT is -hard on two rooted trees.     

Measures of lexical distance between languages

The idea of measuring distance between languages seems to have its roots in the work of the French explorer Dumont D’Urville (1832) [13]. He collected comparative word lists for various languages during his voyages aboard the Astrolabe from 1826 to 1829 and, in his work concerning the geographical division of the Pacific, he proposed a method for measuring the degree of relation among languages. The method used by modern glottochronology, developed by Morris Swadesh in the 1950s, measures distances from the percentage of shared cognates, which are words with a common historical origin. Recently, we proposed a new automated method which uses the normalized Levenshtein distances among words with the same meaning and averages on the words contained in a list. Recently another group of scholars, Bakker et al. (2009) [8] and Holman et al. (2008) [9], proposed a refined version of our definition including a second normalization. In this paper we compare the information content of our definition with the refined version in order to decide which of the two can be applied with greater success to resolve relationships among languages.     

Navigation in tree spaces

The orientable cover of the moduli space of real genus zero algebraic curves with marked points is a compact aspherical manifold tiled by associahedra, which resolves the singularities of the space of phylogenetic trees. The resolution maps planar metric trees to their underlying abstract representatives, collapsing and folding an explicit geometric decomposition of the moduli space into cubes, endowing the resolving space with an interesting canonical pseudometric. Indeed, the given map can be reinterpreted as relating the real and the tropical versions of the Deligne–Knudsen–Mumford compactification of the moduli space of Riemann spheres.     

ML or NJ-MCL? A comparison between two robust phylogenetic methods

Large-scale gene sequencing gives an opportunity to reconstruct the tree of life and histories of multigene species phylogenies from very large datasets. A primary need for reconstructing large-scale phylogenies is a computationally efficient and accurate method. Current efforts to achieve such a goal include NJ-MCL² described by Tamura et al. (2004; 2007), an algorithm based on maximum likelihood (ML) and neighbor joining (NJ) algorithms. Although it has been reported that the NJ-MCL method performs better than the NJ method, studies comparing the accuracy of the ML and NJ-MCL methods are lacking. Here, accuracy of the NJ-MCL and the ML methods are examined. The concatenation approach (by progressive addition of genes) is used in a biologically realistic computer simulation to infer the accuracy of the methods. Simulation results clearly show that although NJ-MCL is computationally efficient and outperforms NJ method, the ML method is clearly much more accurate than the NJ-MCL method. The results encourage the use of the ML algorithm where datasets include up to several hundred species, but for reconstructing grand-scale phylogenies (i.e., where several thousand of taxa are included) NJ-MCL is preferred.     

A lower bound for the breakpoint phylogeny problem

Breakpoint phylogenies methods have been shown to be an effective tool for extracting phylogenetic information from gene order data. Currently, the only practical breakpoint phylogeny algorithms for the analysis of large genomes with varied gene content are heuristics with no optimality guarantee. Here we begin to address this lack by deriving lower bounds for the breakpoint median problem and for the more complicated breakpoint phylogeny problem. In both cases we employ Lagrange multipliers and sub-gradient optimization to tighten the bounds. The bounds have been implemented and are available as part of the package (http://www.math.mcgill.ca/bryant/gotree).     

Slim sets of binary trees

A classical problem in phylogenetic tree analysis is to decide whether there is a phylogenetic tree T that contains all information of a given collection P of phylogenetic trees. If the answer is “yes” we say that P is compatible and T displays P. This decision problem is NP-complete even if all input trees are quartets, that is binary trees with exactly four leaves. In this paper, we prove a sufficient condition for a set of binary phylogenetic trees to be compatible. That result is used to give a short and self-contained proof of the known characterization of quartet sets of minimal cardinality which are displayed by a unique phylogenetic tree.