标题：An Algorithm for Gene-Loss Problem Based on rNNI Local Search
作者：Cui, Meng; Zhu, Daming
作者机构：[Cui, Meng; Zhu, Daming] Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China.
会议名称：3rd IEEE International Conference on Computer Science and Information Technology (ICCSIT)
会议日期：JUL 09-11, 2010
来源：PROCEEDINGS OF 2010 3RD IEEE INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INFORMATION TECHNOLOGY, VOL 9 (ICCSIT 2010)
关键词：gene-loss; rNNI; heuristics
摘要：In this paper, we consider the gene-loss problem which is to infer a species supertree from a collection of gene trees. These gene trees are confounded by complex histories of gene loss and gene duplication events. This problem has been proved to be NP-complete by B. Ma et aI. Existing heuristics aimed at solving the gene-loss problem search the space of all possible supertrees guided by a series of exact solutions to instances of a local search problem. The local search problem is to find an optimal phylogenetic tree in the tree space. We give an effective parsimony heuristics which perform the rooted nearest neighbor interchange operation(rNNI)on an original supertree. Each rooted nearest neighbor interchange operation can obtain a new supertree. The time complexity of the naive heuristics for gene-loss problem on 2-rNNI-local-search is O(kmn(2)). We provide a new algorithm which can solve the problem in O(kmn).