和弦图方法在多状态完美系统发育问题中的扩展和改进。

Extensions and improvements to the chordal graph approach to the multistate perfect phylogeny problem.

机构信息

Graduate Group, Department of Computer Science, University of California, 2063 Kemper Hall, 1 Shields Avenue, Davis, CA 95616, USA.

出版信息

IEEE/ACM Trans Comput Biol Bioinform. 2011 Jul-Aug;8(4):912-7. doi: 10.1109/TCBB.2011.27.

DOI:10.1109/TCBB.2011.27

PMID:21301033

Abstract

The multistate perfect phylogeny problem is a classic problem in computational biology. When no perfect phylogeny exists, it is of interest to find a set of characters to remove in order to obtain a perfect phylogeny in the remaining data. This is known as the character removal problem. We show how to use chordal graphs and triangulations to solve the character removal problem for an arbitrary number of states, which was previously unsolved. We outline a preprocessing technique that speeds up the computation of the minimal separators of a graph. Minimal separators are used in our solution to the missing data character removal problem and to Gusfield's solution of the perfect phylogeny problem with missing data.

摘要

多态完美系统发生树问题是计算生物学中的一个经典问题。当不存在完美系统发生树时，人们有兴趣找到一组要删除的特征，以便在剩余数据中获得完美系统发生树。这就是所谓的特征删除问题。我们展示了如何使用弦图和三角剖分来解决任意数量状态的特征删除问题，这在以前是未解决的。我们概述了一种预处理技术，可加快计算图的最小分隔符。最小分隔符在我们的缺失数据特征删除问题的解决方案以及 Gusfield 解决缺失数据的完美系统发生树问题的解决方案中都有使用。