Schools of Mathematics and Computer Science,Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel.
IEEE/ACM Trans Comput Biol Bioinform. 2010 Jan-Mar;7(1):183-7. doi: 10.1109/TCBB.2008.13.
We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP-hard, so we seek approximate solutions. We formulate the two problems as Steiner tree problems under appropriate distances. The gist of our approach is the succinct characterization of Steiner trees for a small number of leaves for the two distances. This enables the use of known Steiner tree approximation algorithms. The approach leads to a 16/9 approximation ratio for AML and asymptotically to a 1.55 approximation ratio for MP.
我们探索了系统发育树重建中的最大简约法（MP）和祖先最大似然法（AML）准则。这两个问题都是 NP 难的，因此我们寻求近似解。我们将这两个问题表述为适当距离下的 Steiner 树问题。我们方法的要点是，对于两种距离，简洁地描述了少量叶子的 Steiner 树。这使得可以使用已知的 Steiner 树近似算法。该方法对于 AML 得到了 16/9 的逼近比，对于 MP 则渐近地得到了 1.55 的逼近比。
