会议专题

A Faster Algorithm for Gene-Duplication Problem Based on rSPR Local Search

The gene-duplication problem is to infer a species tree from a collection of gene trees. As we know, this problem is NP-hard and thus requires efficient heuristics. Existing heu-ristics for this problem performs a stepwise search of the tree space which consists of all potential species trees. Each step in heuristics is guided by an exact solution to an instance of local search problem. The local search problem is to find an optimal species tree in the tree space. Computing the mapping for gene trees and a species tree is a necessary step in the local search problem. In this paper, we give an improved algorithm to de-termine the mapping between gene trees and a species tree in the gene-duplication problem based on the rooted subtree pruning and regrafting (rSPR) operation. This algorithm eli-minates some redundant calculations and is faster than former algorithms.

gene tree species tree gene duplication rSPR the least common ancestor

Jian Zhang Daming Zhu

School of Computer Science and TechnologyShandong UniversityJinan, China School of Computer Science and Technology Shandong University Jinan, China

国际会议

2010 3rd International Conference on Advanced Computer Theory and Engineering(2010年第三届先进计算机理论与工程国际会议 ICACTE 2010)

成都

英文

1-4

2010-08-20(万方平台首次上网日期,不代表论文的发表时间)