基因组组装问题.docx

数学建模竞赛论文论文题目： 基因组组装问题 姓名1： 学号： 专业： 姓名1： 学号： 专业： 姓名1： 学号： 专业： 2014 年 7 月 21 日基因组组装问题摘要本文主要研究测序策略已知前提下，基于所获读长（reads）序列信息，如何组装出相对合理的目标基因组。本文通过对问题进行分解，预处理相关读长（reads）数据，将问题明确为尽可能使组装序列总长度最大，从而建立了基因组组装算法的优化模型，并根据既有数据对模型进行检验与修正。针对问题一，首先我们将题目分解为三个小模块，包括探析当前主流组装算法优缺点、明确本题模型的评价标准（连续性、完整性、准确性）、分析题目的内涵及具体要求。接着查阅相关文献资料，在理解De Bruijn图核心思想的基础之上，然后根据碱基数目尽可能大及组装序列的总长度的比例尽可能大要求，建立了最终满足所需基因组条件的某一条组装序列的长度Z的目标函数表达式。此时通过分析又可知，Z定然满足与其它的读长序列不能再匹配，又每一个读长碱基个数均为R（常数88），与它相匹配的序列中相同的碱基个数为L，查阅资料并进行相关推导得K（最少实行匹配的相同个数）取4，由于事先预处理了全部相同的读长，故M取87（最多实行匹配的相同个数），并且将reads2中的读长序列全部转换（碱基互补配对原则）进reads1。最后建立了如下的基因组组装算法优化模型：Max Z=Max（W）St.W=Y+R-L +++=R = = = 伴随着模型建立，我们又设计了如下求解基因组组装问题的核心算法：Step1：将原始数据构造成矩阵。Step2：计算矩阵维度m,n（m表示矩阵宽度，n表示矩阵长度）。Step3：赋值，j=1,i=1,k=2。其中j表示忽略的字符数，i表示第i组数据，k表示第k组数据。Step4：将矩阵中两组数据作差（一组数据从第j项到第n项，另一组数据从第1项到第，并且j依次递增）。判断其值是否为0，若真，则记录此时的i，j，k。若假，则继续step5。Step5： ,? 若真，则返回step4，若假，则继续step6。Step6： 若真，则 。返回step4，若假，则结束。针对问题二，首先我们对数据进行预处理，用EXCEL软件相关函数，从两组reads（读长）筛选出所需碱基序列，接着为了降低运算的复杂度，通过MATLAB软件自动读取碱基序列ASCII码值，有效的降低了运算的复杂度，然后结合问题二的已知数据，在MATLAB软件中输入相关求解代码，最后对所得结果进行分析，同时作为检验模型的指标之一。【关键词】读长序列，De Bruijn图，组装算法优化模型一 问题重述与分析1.1 问题背景基因组序列拼接是生物信息学领域的核心问题，测序产生的读取片段reads经过序列拼接组装，生成基因组的碱基序列。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLC方法、贪婪图方法、De Bruijn图方法等。随着新一代测序技术的快速发展，为生命科学重大问题的研究提供巨大帮助的同时，其数据海量、读取片段reads 长度短、精确度低等特点也为全基因组序列拼接提出了相当严峻的挑战，因为一个好的算法应具备组装效果好、时间短、内存小等特点，而传统的序列拼接算法已不再适用。针对新一代测序的数据特点，研发能满足实际应用需要的基因组序列拼接软件，已显得极为迫切，而在这其中，创新序列拼接算法成为了核心引擎。1.2 测序策略 测序策略如下图所示。DNA分子由两条单链（两条平行直线表示），两条直线上相对位置按照碱基（bp）互补配对原则，将一个含120,000个bp的完整基因组，随机打断成500bp的片段，然后对500bp的片段进行测序。测序方法如第3步所示，分别从500bp片段的两端，对两条单链进行测序，测得的读长记为reads1，reads2。reads1，reads2的长度均为88bp，且该对reads相距500bp。（图1 测序策略示意图1.3 要解决的问题利用现有的测序技术，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长（reads）。基因组复制份数约为50–100。本文要求解决如下问题：（1）根据测序策略，基于读长（reads）建立数学模型，并设计相关算法和程序将读长序列组装成基因组；（2）尽量解决组装过程可能出现的若干问题，比如个别碱基对错误、基因组存在重复片段等；（3）建立的模型要尽可能符合连续性要求、完整性要求、准确性要求；（4）根据测序获取的两组读长序列，基于上述建立的的算法和程序，组装一个全长约为120,000个碱基对的细菌人工染色体（BAC）。1.4 组装模型的评价标准（1）连续性要求：组装得到的（多条）序列长度尽可能长。（2）完整性要求：组装序