Genome assembly is a fundamental problem in Bioinformatics, requiring to reconstruct a source genome from an assembly graph built from a set of reads (short strings sequenced from the genome). A notion of genome assembly solution is that of an arc-covering walk of the graph. Since assembly graphs admit many solutions, the goal is to find what is definitely present in all solutions, or what is safe. Most practical assemblers are based on heuristics having at their core unitigs, namely paths whose internal nodes have unit in-degree and out-degree, and which are clearly safe. The long-standing open problem of finding all the safe parts of the solutions was recently solved by a major theoretical result [RECOMB'16]. This safe and complete genome assembly algorithm was followed by other works improving the time bounds, as well as extending the results for different notions of assembly solution. But it remained open whether one can be complete also for models of genome assembly of practical applicability. In this paper we present a universal framework for obtaining safe and complete algorithms which unify the previous results, while also allowing for easy generalisations to assembly problems including many practical aspects. This is based on a novel graph structure, called the hydrostructure of a walk, which highlights the reachability properties of the graph from the perspective of the walk. The hydrostructure allows for simple characterisations of the existing safe walks, and of their new practical versions. Almost all of our characterisations are directly adaptable to optimal verification algorithms, and simple enumeration algorithms. Most of these algorithms are also improved to optimality using an incremental computation procedure and a previous optimal algorithm of a specific model.


翻译:基因组组装配是生物信息学中的一个基本问题, 需要从一组读数( 短链序列顺序由基因组组成) 建立的组装图中重建源基因组。 基因组组组装解决方案的概念是图的弧覆盖行。 由于组装图承认许多解决方案, 目标是找到所有解决方案中肯定存在的东西, 或什么是安全的。 大多数实际的组装者都基于具有核心单位特征的顺势, 即内部节点在水平和水平外有单位且显然安全的路径。 长期存在的寻找所有解决方案安全部分的公开问题最近通过一个主要的理论结果( RECOMB'16) 得到解决。 这种安全和完整的基因组组组装配算法被其他改进时间约束的工程所取代, 以及扩展不同组装解方案解决方案中的结果。 多数实际应用基因组装配法的模型能否完整完成。 在本文中我们提出了一个统一先前结果的安全和完整算法的通用框架, 同时, 也允许简单易变现的算法, 包括许多具体流程的流程的流程的流程, 也是基于一个简单流程的流程的流程的流程的流程。 这要求的流程的系统结构,, 包括许多实际流程的精确的流程的流程的流程的流程的流程的流程。 的流程的流程的流程的流程的流程的逻辑结构, 基础, 基础,, 的流程的流程的流程的流程的流程的流程的流程的流程的流程的流程的流程的流程的流程。

0
下载
关闭预览

相关内容

知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
108+阅读 · 2020年6月10日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
The Measure of Intelligence
Arxiv
6+阅读 · 2019年11月5日
Arxiv
3+阅读 · 2018年2月7日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员