您的位置: 首页 > 外文期刊论文 > 详情页

A Resolution of the Static Formulation Question for the Problem of Computing the History Bound

作   者:
Julia MatsievaSteven KelkCeline ScornavaccaChris WhiddenDan Gusfield
作者机构:
University of California at Davis Davis Montpellier Maastricht WADepartment of Computer Science FranceFred Hutchinson Cancer Research CenterDepartment of Knowledge Engineering (DKE) Seattle Maastricht University The Netherlands CAInstitut des Sciences de l'Evolution de Montpellier (ISE-M)
关键词:
Heuristic algorithmsComputational modelingBiological system modelingClustering algorithmsData modelsPhylogenyHistory
期刊名称:
IEEE/ACM transactions on computational biology and bioinformatics
i s s n:
1545-5963
年卷期:
2017 年 14 卷 2 期
页   码:
404-417
页   码:
摘   要:
Evolutionary data has been traditionally modeled via phylogenetic trees; however, branching alone cannot model conflicting phylogenetic signals, so networks are used instead. Ancestral recombination graphs (ARGs) are used to model the evolution of incompatible sets of SNP data, allowing each site to mutate only once. The model often aims to minimize the number of recombinations. Similarly, incompatible cluster data can be represented by a reticulation network that minimizes reticulation events. The ARG literature has traditionally been disjoint from the reticulation network literature. By building on results from the reticulation network literature, we resolve an open question of interest to the ARG community. We explicitly prove that the History Bound, a lower bound on the number of recombinations in an ARG for a binary matrix, which was previously only defined procedurally, is equal to the minimum number of reticulation nodes in a network for the corresponding cluster data. To facilitate the proof, we give an algorithm that constructs this network using intermediate values from the procedural History Bound definition. We then develop a top-down algorithm for computing the History Bound, which has the same worst-case runtime as the known dynamic program, and show that it is likely to run faster in typical cases.
相关作者
载入中,请稍后...
相关机构
    载入中,请稍后...
应用推荐

意 见 箱

匿名:登录

个人用户登录

找回密码

第三方账号登录

忘记密码

个人用户注册

必须为有效邮箱
6~16位数字与字母组合
6~16位数字与字母组合
请输入正确的手机号码

信息补充