2014深圳杯B题--基因组组装之分析总结

2024-05-10 18:58

本文主要是介绍2014深圳杯B题--基因组组装之分析总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前几天去深圳参加了深圳杯数学建模夏令营,跟其他高校的同学交流了一下(B题),收获颇多,对题目及背景的理解也加深了不少。整理如下(原题在【2014年深圳杯数学建模夏令营题目】可以下载)


解题关键:

1,正确理解测序过程。这个要求详细阅读Hiseq2000(题目指定的测序仪)的测序策略。通过这个测序策略,可以得知:

  • read1和read2来自同一条DNA双链的不同单链,是等价的,没有read1全部来自于正链,read2全部来自于反链之说;
  • 500的长度是大约的值,实际read1与read2之间的距离应该是500左右,而不是确切的500,也就是在程序中只能利用read1和read2的相互关系(有一组称之为共轭互补),但不能利用500这个具体的数。
华大基因的刘心博士一针见血地将测序过程概括为DNA的可放回抽样过程,个人觉得很精辟,为毛刚学过概率论的我没想到-_-||。

2,正确理解质量值。既然题目给出了质量值,并且提到要解决测序过程中出现的个别碱基识别错误的问题,就应该利用质量值做出一定的模型解决错误碱基问题(筛选、剔除),这是一个思路。

3,容错问题。即在组装DNA的时候每两条相邻的read之间允许存在的错误。由于测序的问题,错误是客观存在的,这些错误也将DNA组装问题区别于字符串匹配问题(零容错)。这个需要统计出错期望,设置每条链允许出错的阈值。另外在de Bruijn图中,k-mer的正确选取也可以减少每条单链的出错率。

4,正确理解测试深度。结合可放回抽样的概念,测试深度70*即平均(期望)每个碱基被测得70次。

5,解决基因重复的问题。所谓基因重复问题就是由于生物进化的原因,基因中可能存在某一片段重复多次出现的现象。如果重复片段很短(比如三五十个碱基),则基本可以忽略(因为重复片段短于测序片段88);而如果重复片段很长,比如几百上千个碱基,则必须通过算法加以解决。这是本题的一大考点。当然目前来说还没有很好地方法解决这个问题,只能说仁者见仁智者见智吧。

6,模拟测试。本题只给出了一组数据,而且没有答案(即题目给出的数据是实际测量得到的,并不知道实际的DNA链),所以需要额外的数据对程序进行测试。最简单的办法是利用现有的模拟软件生成相关数据。而我们的失误在于直接自己生成数据,没有想到利用前人的成果。而自己生成数据就免不了理想化处理,这些理想化处理广为诟病。不过这个思路值得提倡。

7,评价标准。这个主要是题目中提到的连续性完整性准确性,具体的评价指标则需要参考文献了。比如contig数目,contig大小,N50,N90,错误碱基数,覆盖度,最长长度等等。另外如果能用自己的程序跑出来的数据跟现有软件跑出来的数据对比评价,嗯,味道更佳。

8,关于查阅资料:广泛查阅,重点参考。例如本题中,要查阅相关生物知识(比如生物DNA特性),测序仪原理,数据格式,测序拼接算法、拼接软件等的资料。在具体解题的时候,不可能广泛参考过多的文献(特别是国赛,时间不够),只能选取其中一些方向参考文献来建模。而我们解题的时候集中查阅了拼接算法的相关资料,却未能更好的利用拼接软件,导致未能站在巨人的肩膀上。

9,创新。由于现有算法很多,现成的软件效果也很好,所以能出彩的地方就是创新。比如自己提出算法,或基于已有算法的改进。说不上那一种创新好,只要自圆其说,别树一帜就能出彩。

10,在几次讨论之后,个人比较倾向于使用de Bruijn图来解决这个问题。毕竟题目给出的数据是用第二代测序技术测得的,read短,深度深,且DNA总长不是很长。但是具体实现的时候又有很多小技巧,比如在节省时间、空间上需要一定的优化。

 

几个思路:

1,预处理。这一步可以利用统计学知识对数据进行第一步筛选,比如剔除出错率较高的异常数据,删除(或者合并)重复数据等。

2,OLC vs de Bruijn。这其实是适用于不同测序策略的拼接算法。OLC适用于长read(第一代测序技术),优点是空间占用小,缺点是速度慢;而de Bruijn则针对第二代测序技术提出,适用于短read,速度快,占内存也大。本题给出的数据是第二代测序技术测得的,也就是理论上说,de Bruijn要好一些。具体算法的实现可以参考相关论文,本文不再展开。

3,还是要利用read1与read2的共轭互补的条件。如果应用得当应该算得上是一大亮点。当然鉴于read1与read2的距离的不确定性,能用上这一点还是有点难度的。

4,有人提到使用动态k值(de Bruijn图的)效果更好,未考证。。

5,慎用概率论建模。个人认为马尔科夫链在本题并不适用。但由于本题的测试深度非常深,可以利用统计学知识剔除出现概率比较小的一些连接,这些数据可以视为异常。当然实际中有很多队伍采用了马尔科夫链,说的也头头是道。保留个人意见。

 

可参考的拼接软件

velvet,SOAPdenovo2

 

涉及到的算法、概念

基因组组装抽象为数学问题即为字符串匹配问题,当然中间还涉及很多统计学、图论的知识。比较有价值的数学概念(问题)有

1,最短超序列

2,编辑距离

3,马尔科夫链,哈希表,压缩编码

4,KMP算法(需要考虑容错),可以参考从头到尾彻底理解KMP

5,N-gram语言模型

6,欧拉图,哈密顿图,深度优先搜索等

 

最后多说一句,获奖队伍的论文将在2015年8月发行(光盘)。且不论结果如何(说得好像你拿奖了一样安静),这次去深圳还是很有收获的。在此也感谢其他参赛队伍的分享!

 

这篇关于2014深圳杯B题--基因组组装之分析总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/977278

相关文章

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析

《MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析》本文将详细讲解MyBatis-Plus中的lambdaUpdate用法,并提供丰富的案例来帮助读者更好地理解和应... 目录深入探索MyBATis-Plus中Service接口的lambdaUpdate用法及示例案例背景

MyBatis-Plus中静态工具Db的多种用法及实例分析

《MyBatis-Plus中静态工具Db的多种用法及实例分析》本文将详细讲解MyBatis-Plus中静态工具Db的各种用法,并结合具体案例进行演示和说明,具有很好的参考价值,希望对大家有所帮助,如有... 目录MyBATis-Plus中静态工具Db的多种用法及实例案例背景使用静态工具Db进行数据库操作插入