Best match graphs (BMG) are a key intermediate in graph-based orthology detection and contain a large amount of information on the gene tree. We provide a near-cubic algorithm to determine whether a BMG is binary-explainable, i.e., whether it can be explained by a fully resolved gene tree and, if so, to construct such a tree. Moreover, we show that all such binary trees are refinements of the unique binary-resolvable tree (BRT), which in general is a substantial refinement of the also unique least resolved tree of a BMG. Finally, we show that the problem of editing an arbitrary vertex-colored graph to a binary-explainable BMG is NP-complete and provide an integer linear program formulation for this task.


翻译:最佳匹配图( BMG) 是基于图形的正弦学检测中的关键中间体, 并包含大量有关基因树的信息。 我们提供了一种近立方算法, 以确定 BMG 是否是二进制解释的, 也就是说, 它是否可以用完全解决的基因树来解释, 如果可以解释, 建造这样的树 。 此外, 我们显示所有这些二进制树都是独特的二进制可溶树( BRT ) 的精细, 一般来说, 是对BMG 中同样解决最少的树的实质性改进 。 最后, 我们显示, 将任意的脊椎色图编辑为二进制可解决的BMG 的问题是完整的, 并为此项任务提供一个整形线性程序配方 。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Arxiv
0+阅读 · 2021年5月1日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员