2014数学建模校内赛提交

1、年“杯”数学建模竞赛仔细阅读了数学建模竞赛的竞赛规则知道，别人的成果是竞赛规则的, 如果别人的成果或其他参赛的题目是：一种基于DeBruijn 图的拼接算法参赛队员 (打印并签名) ：1.日期：年 4 月 27：（reads，法得到原链。本文主要介绍了实现的一种基于 De Bruijn 图的拼k-merk-1：DeBruijnk-mer，Nowadays,themethodofobtainingteticinformationrapidly and accuray makes a big difference in the searching of biology science. We ca

2、n detect numerous of reads of te strand through biology method, then get the original gene strand through Gene splicingalgorithm.ThisarticleintroduceanGenesplicingalgorithm based on the De Bruijn graph.Thisalgorithmpre-treatthereadsbasedonthequalitynumber,then slice the reads into numerous of shorte

3、r k-mer segments. Then build the De Bruijin graph which show the relationship of the k-mer segments, two adjure k-mer segments have the same k-1 bps. But because of the intrinsic lost of information and undetermination of qualitynumber,theDeBruijingraphwillhavethreekindsofbranch structure. Using the

4、 method of evaluation function and setting key- number we can simplification the De Bruijin graph and then montage the contigs. Finally we can find the optimal path of terated graph, filling their gaps, and obtain the original gene strand.Key-Gene splicing, De Bruijin graph, simplification, k-mer, o

5、ptimal (一)背景DNA分子区分开来，但是始终受困于成本高，速度慢的缺点；第台的第二代技术不仅令DNA 费用大幅下降，仅为以前费用的百分之一，并且让组这项以前专属于大型中心的“”技术能够献。第二代DNA 技术有助于人们以更低廉的价格，更全面、更深入地分析组、转录组及蛋白质之间交互作用组的各项数据。它将组若干份，无规律地分断成短片段后进序，然后寻找测得的不同短片段序列之间拼接算法对提升组的精确度有重要作用。（二）算法综基于DeBruijn图(DBG)策略的拼接算法被最广泛应用到新一代数据的DeBruijn小），作为图的边，相邻的两个 k-mers 交叠(k-1)个碱基；DeBruijn构建

6、 列即为 contigs；生成 DeBruijn DeBruijn readsreads得到 DN段，而碱基对配对方式只有 4 种。因此出现碱基错误拼接的几率不注：式为碱基的质量值， 为出错率DeBruijn首先，从 reads 上的首碱基开始，依次截取 k 个碱基，作为续子串 k- mer。由于在获取 k-mer 的过程中会出现大量相同的 k-mer。因此，每产生一个 k- mer，都需要记录其出现的 reads 和 reads 上的起始位置，还需要记录其出现设计数据结构编码，记 A(00)，C(01)，G(10)，T(11)；k-mer 依次 reads 文件中的每条read并根据k 值的

7、大小截取连续的k-mers。对从read 取得的每个k-mer，通Hash k-mer De Bruijn 图中的地址，若该 k-mer 存在，则计数增加 1；否则开辟新结点； 依次 reads 文件中的每条 read，取得其对应的 k-mers。对于取得的每个 k-merHashk-merDe Bruijn1曾培龙基于reads引导的组序列拼接 在完成上述两步之后，如果候选 k-mers 为空，并且已经处于第二轮拼将 contigs 反向互补，选择新的 k-mer 进行拼接；DeBruijn reads k-mers 为删除状态，将成功的 reads 添加进 contigs； read 的

8、reads 数目小于特定的值时会引进新的 reads； 则作为当前的 k-mer 的最终得分；会出现。拼接错误一般是单碱基错误，该种错误可能导致的 3 种拼接情形。 允许出现 1 次，同时不允许出现其他类型的错误(如 b c);且不允许出现情形(a, c);允许出现情形(a, read 其中拼接成功的 reads 及其方向将被记录在 contigs 上，以便第二阶段 k-mers reads 评分原则为2contigs 如果被配对的reads上的两条contigs之间有交叠，则配对的两条readsreads数目达到设定的阈值，此时认为两条 contigs 在是相邻的，应该连接到一起; 的 ga

9、ps 填充操作。拼接错误的解决方案在contigs 的构建阶错误通常发生在contigs 的末这是因为contigsLbp长的序列片段，这样既减少了内存消耗，也有利于提高计算速度。如果 contigs 的长度小于 L，则取其整个序列。contigs连接 由于contigs 之间的相对位置己经确定，可以根据相邻两条 contigs 上配reads 来计contigs 之间的distance，从overlap 的大小。此时的 distance 大小可以大于 0，也可以小于 0。在 如果contigs 之间的overlaps 大于设定的阈值，两条contigs 就可以通过overlapgapscon

10、tigs contigs contigscontigsgapsgaps 填2 曾理等使用分布式DeBruijn图遍历拼接并行构建和化简3 王东阳，任世军， DNA序列拼接中DeBruijn图的研究gapscontigs之间缺少的那部分碱基序列构造出来。配对数据往拼接生成的contigs 上时，有这样的一部分配对的 用这些reads 就可以很快速的对 contigs 之间的gaps 进行填充。readscontigsreads拼接部分，需要先后两次数据文件，然后根据决策表构建De Brujin 图。为提升准确率，由于错误33种拼接情形。故针对这3 种情形进行即可。在contigs 组装部分，涉及

11、相对位置的确定、contigs 连接以及 gaps 填充。（四）具体实（BAC，采用Hiseq2000 仪进序，策略以及数据格式的简要说 明见附录一和附录二，测得的读长数据见附录三，深度（sequencing depth）约为70，即组每个位置平均被测到约 70 次。试利用你的算法和程序进 AAGTGTCAAGGATCGCGCCCCTCATCTGTCAGTAGTCGCGCCCCTCAAGTGTCA CG GATTACGCCAAGCTATTTAGGTGAGACTATAGA TCAAGCTTGCATGCCTGCAGGTC ATCTTAGAGAAGACCTTAGCTCTAGCTAACTGGTCAAA

12、AAGCACATCA GGGGCAAC AATGTACCCGTCA TGGTGCTCCCTCTGGTAGATCAACCAATGTGGTGAAGTTTAAA TGGTGGATCACCATTACATAGAGGTCACTATGTAGCTTCTAGGTACACAAAAGA TC ACAAGTTCAACATTATTACAAACCAGGTTTTTC ATAGAAGTAAACATGGTTCAGAG TTTAAACAGCGGAAAGTAAACTACACGCATG ACACAGGAGGCCATCCATGCATATC TGGGATTACCTGAAAACAACAAATTAAGCAAGGCTGAGT TATCAGCA

13、AGACT （五）总结组现在已经成为生物学领域的问题之一。本文主要介绍了一成链片段，并且较好的解决了中可能出现的个别碱基对识别错误（主要通过质量值预处理、组中存在重复片段（主要通过简化De Bruijn 图以及引入 k-mer 估价）等复杂情况。该算法可以较为便利的实现并行化。目前由于硬件环境限制只实现了串行程序，但是将来面对更大量的拼接工作，可以容易的将程序并行化以附录二TTGTGGAGCTTAGAAACTATGGCAG CATGAAAGAGTTTGTTACATTAATTGTGGGA cCCGGAAACATCTCTCAAAGAAATTCTATGCCTTTGAA AATCTACAAATCGAT

14、TTAT ACCAATCGCTAACGTCATTTTTG GACCCATTTTATTAATAAACCATTTTTGAATTC CAGTAATTAACATCACAGATAATATTTCC CACTGAAATAAATGTTTCGGATC AGCGCAGGAGACAACAGGTTTTTGGTTCGGGCCTCCGAGGAGTA CCTACGTC T GAAATCGTTTTACAGAGGCTCCAATAGATGACACAAATGTATGGGAGCTACTCAC GCTGATTAGGTTTAATCTATTCCAAATATATTTGAGC TCACCATTCGAAATTCATA TGCTTAAAAGGTA

15、TAATTT TTCTCTCTTTCTAATTAAAATGTGGTTAATCTATAAC TCACGACATCTCTAGACGATCTG CCCAAGGACTTCAAACCAGCCATTGAGAAGTAC CTTACGTGACACAGGGATTCGTATAAACGCATGGC GGATTGGTGATTTCTTT GGTCAATCCGAATATTTCAGCATATTTAGCAACATGGATCTCGCAG CGTCATGTTC CCGTTTTCCATGAGCAAACTGAAACGTTTTCATCGCTCTGGAGTGA CACGACGATT AATGTACCCGTCA TGGTGCTCCCTCT

16、GGTAGATCAACCAATGTGGTGAAGTTTAAA ACAAGTTCAACATTATTACAAACCAGGTTTTTC ATAGAAGTAAACATGGTTCAGAG TTTAAACAGCGGAAAGTAAACTACACGCATG ACACAGGAGGCCATCCATGCATATC CAAAAAATCATAACTGAAAAT CCATCAAAATCATGCAAACTTTGGTCATAGATCTA AGTAATAAACGAC CAACAGATGGAGCATTGGCAGGTTCTGAAGCTGATGGTTGCTG TCTCTAGGAACACAACTCATCTC AACTCACGGCGCA

17、CTATTGCACCATCTTGTAAT TTGTTATTGGTGCGAAAATCCAGGTATAAAGAGTTGGGCTGCATTC TCAAAAACCC GGTTTTGGCTCTTTTATCTGCAAGTATCCTCTT CAATTTCTCCAACCTGCAATTGG ACATTTTCCAGAAATGTTTACATTCATGTTGCAAGAA CTAGAGGTCTAATAGTTCT AGGTTGTGTATAGACTATCGATCACTTAATGAGGTTACTATCAAGAATAA CCTTTA ATAAGCTTCCTTGGACTTGCAGG TATCGGAGGTTCATTGAAGGATT

18、TTCTAAGATA AAGAT TGGTGGTATGGGATGAAGAAAGATGTAGCAGCTCATGTAGCTTTGTGTGAT CTTTTCTCTTTCTCTTCTTTTTCTTTCTCTC ACATATTTTTCTCTTTCTTTACTTT TCTATTTTTTCTTTCTTTCTTTTCC TC TTTTCTCTTTATTTTTTCCTCTCTT AATAAACCATGCTAG AAGACGAAACTTTGAAAGTAGGTTGTGTTCAAGGAATGTGA ACGGATTCG TTGGGTTCACCACCCGAGGGAAGAAGGGTCCCTTGACTACGACGGGA GG

19、CTTGTCCTCTTGCAAGTCTAAACAAACTTTG AACTATTAACCGTCAACAAGCCC AGTTCAAGGCCAT AAGGTGTTGGAGAACATCGATAGTAAAGTGACGGAGGTCGGAA AAAAGATTAATCCACCGCATG AATCTAAACATGGAAAGCTAAAAGCATGCACTGCT A AAAGGCTCCACAAGGCAAACAGGAGTGAAGTCAGGAAGCGG AAGTCATATA TCCAGAATCACATGAAAGACGCCCTCTGGGTGAAGTCGA ATGGCGTTCCTGAACAT AGGTACCTTCAGAGG

20、CTGAAGCAATATTGCTGGCCTTTG TCAGTCTTCACTCTTTG ACAGACATCACACAAAGCTACATGAGCTGCTACATCTTTCTTCATCCC CACCAGTA AGTAAAGAT TTCAGACTCTTATGGTCAGTAAAGATCTTGCACTTGTTTCCAATCAT AAAGC CTAACACCTAGTTCTCTAGTTATTAAGCCAAGACAGAGCCATATGTCTTGT AAG AGCTAAAACAAGTTTAGGGATTAATCTGCAAAGAAAAACTAAGTTTCGGGCTA TATCGTTATTC CACCTATTACACC

21、ACACACACAAAAAATT GGCCCCATGAAGTCT CCCACACATCGAATAAATCGATTTGTAGATTGTATTTCAAA TTGTTGT TCCTCTTGAACCCGAGGTTTTGACAGTCGAAACTTTGTTGTATGGACCG TCAACAACC CACCCCGGACGAATTAGTTCAGGTTCACAACACTTCTCGTTCCCCGT TCGTGTCTTCTGATCGCAGGAATGAGTCAAG CTTAAAATGGAAACTCTTTGTATTA AAATAATTTGAATCTGCACTTATGCTTTGGTCAGAAGCTTATTTTGGC AT

22、GACTTG AGTATTAGT TCAGCCTTGCTTAATTTGTTGTTTTCAGGTAATCCCATCTGGCCTGG ATTGGTTCGACCTTTGA CAAAAATGTGAGTTATAACCTTTTCGAGTTTCTCACAGA TGTTGCGCCAA TTCAGACTCAACAACAAATTGCACAGAGGTTGCAGCAGCCTTTCA ATGAATTGGATGACTCAGC AGTTGTCCTGGATATTTCAGAGAGAATGTTAGAAATC TAGACGAATTGATAAGGGGTC CTATCAGTGTCTTGAACGCCGTTCG GCCCAC TCCTCC

23、ATCCACGGGGACTGAGAGCCATTGCTATTGCTGTATTTGGTAAGCAAA GT ACCCATCCGTG ATTGAGGCTGTTCCCTGGGGGTCGTTACCTTCCACGAGCAAAACA GTTTGGTGTACCAAA ACCGTCAACAAGTGCCGAGCAAGGAGGTGCAGCCGTATCTC ATCCGTCAACAGCACTGCAGCTCCCTCTCACCTACAA CCCCTCCTGTAGCCACCGA GTA CATTGCAGTAATAAAACGTTCAAGAGTTAAACCAGTATGATATCCATTATTAC GGAGG ACTGCAAGAAACATTCAAATTATTGCAGCCATCCAAACCAATGCAAACTAA TACCAATTAGAAACACTAAGACATTGAACTTTTGTGAACAAAACCTACAA TT AAAGGCCCTGCATGGTCAGCA CAATTAGAAACACTAAGAGATTGAATTTGTGTGAA TAAGGTT ACATTACTGAATTCAATGTTTAAATATAAAACACCACAACCACCTTT