P=i-k j=1,i=1,k=2 矩阵维度m,n 构造原始 数据矩阵D 开始 NP=0 Y j,i,k k=k+1 Y N k?m i?m Y N i=i+1 k=i+2 结束
5.1.2建立de Bruijn图方法模型
基于de Bruijn图数据结构的read之间对比拼接算法可概括一下几个步骤：
(1)把筛选过得序列集合S作为参与比对的read库； (2)确定k值，建立de bruijn图。这是需要扫描所有read数据，将每一个长为L的read拆分成L-k+1个k-mer,并用所有read的所有k-mer来累加，建立节点和边都加权的de bruijn图；
(3)化简de bruijn图，连续线性延伸节点合并成为单一节点，产生一些碱基序列更长的节点；
(4)遍历de bruijn图产生contig。
以上是对基于de bruijn图的算法做了简单介绍。de bruijn图是一种特殊的加权图，不仅图的及节点上有权值，而且边上也有权值。使用de bruijn图只能将较短的read拼接成较长的contig，要得到全基因组，还需要contig的组装过程。
contig的组装，即可以将read转化成定长的k-mer，并将这些k-mer存入be bruijn图中，以备之后查找使用。此时要设定的一个重要参数是k-mer的长度。选定k值之后，要将长度L的read拆成L-K+1个k-mer。
根据一定策略，选定一个初始k-mer，接下来就可以在该k-mer为结点开始搜索后继的k-mer。搜索时采用贪婪图策略，每一步选择在当时看来最优的后继k-mer，直到满足事先设定的终止条件，结束一条contig的拼接，接着开始下一条contig的拼接。直到没有合适的初始k-mer可供选择，整个拼接过程结束。
de Bruijn图的拼接算法的核心是K值的选择方法，本文假设出现4个碱基相同的视为巧合情况。故将K=4进行研究，这样使得de Bruijn图有相对好的连通性。
下面简单用一个例子表达以上模型的含义: 将基因组复制若干份，无规律地分断成短片段后进行测序，然后寻找测得的不同短片段序列之间的重合部分，并利用这些信息进行组装。例如，若有三个短片段序列分别为：
ATACCTTGCTAGCGT GCTAGCGTAGGTCTGAGCTTAACT GCTTAACTGTTACCAGATC
则有可能基因组序列中包含有
ATACCTTGCTAGCGTAGGTCTGAGCTTAACTGTTACCAGATC这一段。 我们的程序就是按此方法，一步一步找出最长的组合完成之后的序列。
5.2问题二：
对于问题二，我们在问题一的基础上，将所给的读长数据进行提取，导入matlab软件中，结合问题一解答所编写之程序，运行后得出结果。
现在我们就可以用问题一的程序来解决问题二，并让显示的结果来验证问题一所建立的模型的组装序列的连续性、完整性和准确性。
首先我们利用编写的程序（见附录程序一）将原始数据进行提取，得出一个只包含碱基序列的文本，并将其导入matlab软件，结合问题一模型所编写的程序，得出问题二所要求的组装后的DNA序列。（由于数据量较大，假若将完整DNA打乱之后的全部片段导入并运行程序，耗时相当长，而且后续结果也难以处理和展示，所以在此我们只提取碱基序列文本的前10000行碱基序列进行组装），组装结果如下：（因为基因的起始序列不同，所以程序运行完毕会得出多个结果，在此我们选取较长的几个结果序列表示出来）
结果一：
CGGTTAGGGTTAGCAATAAAACAAAAATCTAAAAAGAAAAGAAAAATTAGGGTTAATCAAGACCTAGATTAGATCGATTTTTTCTTTTGACGAGTCTCGGTAAGACCATGAGAAGCTTGTCTTGTTTTGACAACATCTCATTTATAATATTTTGGTAGGACTAAACTTTCCCGCGCTCGAAAACATGACCGGATGCTCGAGTTTGAGCTCCTCCGGCGAAGCACCGCCGGGTGCCGCCGTCTCCGCCGCGCGCCGCACAACACATCGGATACATCCCGAAAGGGTCGTCATCGCCAGGGTCTCCGCCGTCATCACCATCTTCATTGTCGTCGCTGCCGTCTGGCAGCGCTGTCGCTGGCGATTGTCATCAGTGCGCTGCTGGTGAACGCTGTGGGGATTATCGGCTTTATCGGGTTGTTCGCGC
结果二：
AAATATGACTCGTGCAGAAGCATGGGCTGATAGACTAGTTTTCACAAATTTAGATTCATAGTCGTTATTATATATCTACTAGACACAACGTTTACATGCCCTTATGGAACATTTCCATATAGAAGGATGCCCTTCGGTCTATGCAACGCTCCAGCCTCTTTTCAACGTTGCAATACACCACTTTGATTTAATAGTGGGATTGATATTCTTTCATGTCATCCCTTGTCTACTCACCTCCTTATATCTTCCCATGGCTGGAATCCTTGCTCCACCAAAAGTAGCGGTAGCCAGTTGATCAACATGTAGACCACCAGCAGAGTGAAGAAATAACAAAACCACAATAACTGACCAAAGGTAAACTGAACTAACAGGAGAAATAAATAACAAGGTAAGCTCTAAAGAAAGGTATCTCCAAAAGATTGGGCCGCGGGGCTGGTGGTGGGCTGCGGCCGGCGCTGGGCCAAAAGGGAAAAGAAGGGGGAGTTAAAAGGGAAGGGGTTCTTTTTATGTTTTAAAGCAGTGCATGCTTTTAGCTTTCCATGTTTAGATTGTATCATGCGGTGGATTAATCTTTTTGTGGTTAGTGGTGTCAAACCTGGCGTCTATGCTATTTGTTGGGTGAGGCTGGAAGTGGAAAAACCTGGCTGGCGCAGCAACTGCAAAAAGATAAACATCGTCAAAAGGACATAACAAAATTGATCTATTATCCAGCTCCATTTCTTGTGTTGCCTCTTCTCGTAGGAGGGGATGTTTCTACAACTTGTCTTCATAAGATAGCTTACCTTGCTTTACTAGATTGAATCCTTGCGTTGCACATTGTTCCACGGATTCGATACCTTGGGTTGAAAATACAAACTTAACGACCATCAACATTGTTCAGTGTTCATTGATAATAATGTGTTGTGTGTGATCCGAAACATTTATTTGTACACTTTACCCACAACTCGTGTACCCCATCTTGCCCGGGTTAGCCAGACCCTTAAACACTTCCAAGGTGAGTGGCTAAGGGTCCCTGTTGATACCGGGAAGCCCTGGGCCAACTTTTGGCGAAAATGAGACGTTGATCGGCACGTAAGAGGTTCCAACTTTCACCATA
结果三：
GTTCAAAAGAGAATTCAAAGGGGAGAGTTAAATTGTCATTGTTCAGATAAGGGAGCCAAAGAGGATCAGGGAAGCCTTTGAAGAAGAGTGTAAAACTGATCGATCAGCCGTGCTCACGGTCATGAGCGGCTTGGACCCTCACATGATTAATAAACTTGAAGAATAATGCGAAACCCTGAGGGGGGGCGACGGAGTCCGGGGCGCAGCGTAGAGAGGGATCGACGACGGCGGCCGAAGATTGAAGACGGCGACGGTGGAGCGAAAAATAAGTTTGGCTTTGTATAGGATTTTTTTCTTACTCTCATCTTGGAAAAAGAGGATTTGCTAACCTTTATCACAAAAGTTGACACATGAAGATGGTGAGCTCCAACAGGAATCATGAAGATAGAGGTAATGAAGGAAACATCAACTTTATTGTTTGAGCAGAGAAGAGAGGGACACCATCCTGGAGAGGAGAGGGTCGAGCTAGTTGACTAGAGTCTCTCTAGCCGACGTGGGAACCTTGCAAACAATGATGAGAGAGGTTATAGCTAGGTTGTGCTGGTGCG
ATAGGGATGACCACGAGGTTGGGGATGTGTGGGTGCGACGAGGTGGGCCGGCCGCACCTAGAGGGTCAGCCACTACGTGAAAAACTCGCTTTGGTAACAGGCATAGATTGCCTTTGGTAACGGGCAATAATAAAGAATTATTAAGTCGCTTCCGCCGGGTAAAGCCAGGTGAATCACTTATAACAGGATCGAGATATGCGCTAAGCCCACACAACAAAAAATGATGCACCAACATGTATGCAACAGGGAACTCCAATATTTCATTATTAAATTAAGAAAAATGATTAAATGCCTATCTTATGAAGACAAGTTGCATCTAATCTACTAACTCATAAAAGAAAACACATCTAATCTAATATACTAAAGAGGTAGCACGAGAAGAAGAAGGGCAGGCCTATCCTGTTGAACGACCTGTGTATTACGTAAGTGAGGTCCTGGCTGACACTAAGACACATTACACACAACCCAGTGGATGTACCAAGTAGCTCAAGTGAGACGACCAGCCAAGTCATCCGCAATAACTCGATGAAGGTCCTATAGAGCGTAGAAATTTTGAGAAAGTGCCACTCGACGGAGTACGGTGGACACTATAGACATTTTAGGACCCAAGCAAAAGTGTGGTCTAGCAGATTGAATTTGTGTGAACAAAACCTATAAGAAACTGACTAGTTCCAAAACAGGTTGGAGGTCTAGGAACTTTTACGGGGGATGTCGTTCGAAGGTCGGCGCGCATCCGTGGCATGAAGCGGAAGGACTACAAGGAGGTGTCGCCCGAGCCTAAGGACTATGGGGATAGCGACGCCAACAGCCGCATCATCAAGTGGTCGGTCGAGCTTGGAGAATTCGACATCGAGTTTTGCCTCCGGCAAGCGATCAAATCGCAGGCGTATTACTCATCTCTCCTCAGGGGGAGTAGCTTAAGTACGTACTGCAAATTCACTACAAGGCCTCCAACAACATTGCAGAATTGGCCTTTGCCCCCAATTGCAGGTTGGAGAAATTGGTATAAGAGGATACTTGCAGATAAAAGAGCCAAAACCAGCAATTGGGACAAGGACAAGCGGCGACCGAGCAAGAGCGGCTACAAGAAGAACAAGGCAAGAGCGATGGTGGCCGGTGCGAGCGACGTCGACTCACGAAAGCGTCCACATTCATTACCGTTCACTATAGAAACGGTATCCATGCATAAAGCCGCTACATGGACAGCGTCCTAATTAAGAAGAAGAAAGAGCCGAAGAAGAAGGACGTGAAGAAAATCAAGGAAGATGTTGCATCCATCAAGACAAAGGAAGAAAAGCCGCCTGGAAACATTCGTCGACCGATGCGTAGAACTCCGAGATGGATTGACGGCAAGCCGCACAACACATCGGATGCATCTCGAAACGGTCATTGGCTTTGAAAGGTAAACAACCATTAGAGGAAGTTCTTAGTTTGACAATACTTGTGTTGATTGTGCTAGCCATACCTATAGCGGGACGCCCAGTCTTTGGCCAGACGGCTGCATCTCCGACTAGTTTCCCACTAGAGGAACCCTCGCACGACAAGTCTCCGCCTCCCATTATCGTAGAGATCCGCATTATTAATCTCAGGAGCCTGTGTAGCGTTTATAGGAAGTAGTGTTCTGTCATGATGCCTGCAAGATGGCCAAGCCGTCCAACGAAAAAGACATCATGAAGCTCACAGGCATGATGGTGGCCCTAGGTCGTTTCATCAGCAAGCTCGGCTGGTTGCCACTGGCCTTTGCGCTCGACTGGAACCGACCACCGCGCCAAATGAACAGCACCTCGTTTTTCTACAATCATTCCCGCCATTGTCCTTCCACCACCTAATGGAATCTGGTCGTCGTCGTCCCTGAGTTCCCCTCGTTCTTCTATTCCTTCTCCTTTCCTCAGCAGAAGGAGCGTCGACAACATTAGGAGGAGCCCAGGCAAACTACGCCTAAGCAGCAGCTGCAACATTAGGATAAGCAACAGACGGCGACGGTGCTCCGGGTTCCGCGGCTCGATCCAGAGGCGAGGAAGGGCAGTCCTGGTACAGATAGAGACCACGGGTGAGCGCCTTTCAACGCAGTAGAGGGAATGCCGCCTACGGCATCGGCACCGCGCTCAATTTCTGCCAGCATATAGCCCATTCCGTCTTGATCGATCAGTTTTACACTCTGCAGAGGTTGTACACTTTACCCACAACTCGTGTACCCCATCTTGCCCGGGTTAGCCAGACCCTTAAACTTCTCAAAGTGATTATCAAGTTTACCTCGGAAGTAGAGTGGCTTGAGTTGTGGTATCCTCGTGTCTTCTCCCGACATCTCAAACATTAGACTTAGAATGGTTGAACAATGTTAGAGACATAATTCTTGGTTGAATATTTTGCTTTGTCATAAACCCTTTGCATGAACCATAAGCACACACATACATGTATATCATCCAAGCTATCATGATCAATATTCAACATATTGCATAAGATTCATTTTAACAATCCCACTCGTATCGTCGGTCTGATTATTAGTCTGGGACCACGGTCCCACTCGTATCGTCGGTCTGATTATTAGTCTGGAACCACGGTCCGTTTTCGCGCACAGCACCATGACCGGGTGGTAGTCATCTGCCCGGGGCGTATTGAGAGCTACGTAAAATATGCGGAAATGGCCTACAATGGCATGGCCGCAGGCTTCTTCAATGGCGACTGGGGAGTACTGCTTACCGCGCTGGCCAGTAACAATAAAAATGACATCCCAATTCGGCTGTACATCTGTATTCGGTTGTGCTTTCATGAGTAAAATGTGCTCATAATTTATGTTTTAAAGCAGTGCATGCTTTCTTTAGACTTCTCTGACAGGAACAACAACTTAAAGACCGCCTGGGACAGCCTAATGGAAGCTGCAAGCCATGGCAATCCTCGAAGGTCTTTACAACGATCAAATGTTAACTATGAAGACGCAACTCCATCTTCATCTTCCACAGGCACATGACTGGGGGCACGCAAGCAGGGGCCTATTCGTGAATCTGGAATTTAAGACAAGGGCTCCCCCTGTAAATG
