New fixed-parameter algorithms for the minimum quartet inconsistency problem
學年 97
學期 1
出版（發表）日期 2009-01-27
作品名稱 New fixed-parameter algorithms for the minimum quartet inconsistency problem
作品名稱（其他語言）
著者 Maw-Shang Chang; Chuang-Chieh Lin; Peter Rossmanith
單位
出版者
著錄名稱、卷期、頁數 Theory of Computing Systems 47, pp.342–367
摘要 Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4k n+n 4). In this paper, first we present an O(3.0446k n+n 4) fixed-parameter algorithm and an O(2.0162k n 3+n 5) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O *((1+ε)k) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant.
關鍵字 Evolutionary tree;Quartet topology;Leaf-labeled tree;Minimum quartet inconsistency problem;Fixed-parameter algorithm;Depth-bounded search tree
語言 en_US
ISSN 1433-0490
期刊性質 國內
收錄於 SCI
產學合作
通訊作者 Chuang-Chieh Lin
審稿制度 是
國別 USA
公開徵稿
出版型式 ,電子版,紙本
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/120037 )

SDGS 優質教育