Approximating Minimum Quartet Inconsistency (Abstract)
Gianluca Della Vedova, Tao Jiang, Jing Li, Jianjun Wen · 2002
A fundamental problem in computational biology which has been widely studied in the last decades is the reconstruction of evolutionary trees from biological data. Unfortunately, almost all its known formulations are NP-hard. The compelling need for having efficient computational tools to solve this biologcal problem has brought a lot of attention to the analysis of the quartet paradigm for inferring evolutionary trees [1, 2, 8]. Given a quartet of taxa {a, b, c, d}, there are 3 possible degree-3 trees connecting the taxa as terminals. Each such tree is called a quartet topology. The quartet methods proceed by first estimating the topology of each quartet of taxa and then recombining the inferred quartet topologies into an evolutionary tree. A major difficulty in this approach derives from the fact that quartet topology inference methods often make mistakes, and thus may result in a set Q of quartet topologies that is inconsistent with any evolutionary tree. Therefore, the problem of recombining the quartet topologies of Q to form an estimate of the correct evolutionary tree is naturally formulated as an optimization problem that looks for a tree T maximizing the number of consistent quartets (i.e.