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

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库:创建新文件夹,进入文件夹目录,执行指令 git init ,用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者

MOLE 2.5 分析分子通道和孔隙

软件介绍 生物大分子通道和孔隙在生物学中发挥着重要作用,例如在分子识别和酶底物特异性方面。 我们介绍了一种名为 MOLE 2.5 的高级软件工具,该工具旨在分析分子通道和孔隙。 与其他可用软件工具的基准测试表明,MOLE 2.5 相比更快、更强大、功能更丰富。作为一项新功能,MOLE 2.5 可以估算已识别通道的物理化学性质。 软件下载 https://pan.quark.cn/s/57

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000

状态dp总结

zoj 3631  N 个数中选若干数和(只能选一次)<=M 的最大值 const int Max_N = 38 ;int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ;

ZOJ Monthly, August 2014小记

最近太忙太忙,只能抽时间写几道简单题。不过我倒是明白要想水平提高不看题解是最好的了。 A  我只能死找规律了,无法证明 int a[50002][2] ;vector< vector<int> > gmax , gmin ;int main(){int n , i , j , k , cmax , cmin ;while(cin>>n){/* g