SPDP基因限制性图谱重构结

第1页共12页DNA限制性图谱绘制论文摘要本文首先证明了该问题不存在多项式算法，最坏情况下其时间复杂度不低于指数。进而在穷举法基础上提出了一种优化算法，该算法通过分析所有的DNA片段数据，建立了b-b表与b-c表,利用两个表的逻辑、几何的关系对穷举二叉树进行预测，对穷举过程进行强限制，极大优化穷举法。文中并应用计算机实践报告与复杂度理论分析对所提出的算法进行了深入的测试与评估，对于稀疏的数据该算法时间平均复杂度是多项式。在解决了一般SPDP问题后，针对带误差的SPDP问题，通过对误差及概率的讨论给出了一解法，解决了含有误差的SPDP问题。在原有SPDP问题上，考虑实际需要，对SPDP问题进行分析，提出了改进方法，并对于一些特殊情况进行了讨论。关键词：DNA限制性图谱SPDP算法第2页共12页PDP部分消化法利用限制性位点酶可以将DNA分子中的限制性位点切开，假如一个DNA分子有n个限制性位点，利用不同的限制性位点酶，通过大量实验得到任两个限制性位点（包括两个端点）的长度，共222nC个值，把利用这些数据作为第一组数据，PDP方法就是利用这组数据重新构建DNA限制性图谱。例如：={2,3,4,5,2,5,9,14,16,7,12,14,9,11,7}图1图1中A,B是DNA分子的两个端点。a，b，c和d是限制性位点。通过实验可以得到={2,3,4,5,2,5,9,14,16,7,12,14,9,11,7}.再通过来求，对应于上图的={0,2,5,9,14,16}是一种解。SPDP简化部分消化法鉴于目前的实验技术所限，PDP的方法实行起来有相当的难度，所以在PDP的基础上得到了SPDP方法。SPDP方法不需要得到任两个限制性位点的距离，只要的测量任一个位点到两个端点的距离，作为第一组数据，以每段DNA片段的长度作为第二组数据，重构DNA限制性图谱。图2中（a）就是我们希望重构的DNA图谱，（b）中的前4对图谱为第一组数据，它的每对的长度和都是16，剩下的为第二组数据，含有5个片段的长度，是由（a）每段都切开以后得到的。SPDP方法就是要利用(b)中的数据通过计算重构图谱(a)的结构。第3页共12页DNA限制性图谱绘制在目前的技术条件下，SPDP是一个可行的办法，但是SPDP的实验数据只有不完整的片段长度，需要对这些片段长度进行数学处理才能得到原始的DNA限制性图谱，本文第3部分中面对生物学对SPDP问题的求解需要，给出了一个完整的SPDP问题的解法。1建立数学模型以及SPDP问题算法利用SPDP方法重构DNA的顺序时，已知的数据有两组，若一段DNA的位点总数为n，则第一组数据是通过对位点进行一次切割而得到的2n组数据，第二组数据是切开所有的位点得到的n+1个片段的数据。从第一组数据入手，进行一定的组合，而利用第二组数据对第一组数据的组合进行检验。这里，我们首先要对第一组数据进行一定的处理。在第一组数据中，DNA都是被切成两段，当DNA总长度L知道的时候，其实只要知道每对b中的一个值就得到了全部的信息。现在我们将每对b中较小的一个挑出来（若ib与ib'相等任取一个就可以）。这样我们就得到了n个数据，再对这n个数据进行升序排列，得到一个不严格递增的b序列，在这里不妨记作nbbbb321，，，它图2第4页共12页们满足2321Lbbbbn，它包含了第一组数据的所有的信息。为了方便计算，我们不妨先对基因图谱的起点和终点做一个规定，假设从起点算起，第一个位点到起点的距离小于或者等于从终点算起第一个位点到终点的距离，即11nkkcc。对于重新组织后的第一组数据，其含义为：对于某一个ib，它表示离这段基因起点或者终点ib距离的位置有一个位点。则对于第二种穷举方法也就由此而得出，对于每个ib它有两种状态，一种是靠近起点（不妨用“0”表示），另一种是靠近终点（不妨用“1”来表示）。而当全部的ib的状态确定后，DNA的顺序也就确定了，但此时要对这个顺序的合理性进行检验，即检验这个顺序是否符合第二组数据c的要求。具体措施如下：将“0”状态的ib全部挑出来按照升序排列lssssbbbb3121，，。再将“1”状态的ib全部挑出来按照升序排列nlllssssbbbb321，，。记第二组数据c组成的集合为}{1321nccccC。然后检验是否满足以下条件：CCbs11（前半段）112/12sssbCCbb)/(122323ssssbbCCbb……)/(2111llllssllssbbCCbb)/(111lllssllsbbCCb（后半段）112llssCCbbll……)/(2111nnnnssnnssbbCCbb)/(11nnlnssnnssbbCCbbL第5页共12页当全部检验条件符合的时候，这组组合即为合理的顺序，从DNA的起点算起，在前半段的基因中，第i段长度为1iissbb(其中00sb)，而对于后半段则有相同的处理，其示意图如图5表示。流程图如图4表示。这里值得说明一下的就是对与这个循环的结束条件，因为对于基因的排序问题，必须要求出所有的可能解，因此对于这个循环就必须要把所有的可能组合全部进行一遍以后才可以停止，即需要循环n2次。分析这个模型以及它的穷举方法可以容易的发现，对b进行组合时的复杂度为n2，而每次判定组合是否是合理的组合还需要利用查找函数，复杂度为n2log。所以总的复杂程度在nn2log2以上。因此我们可以看到，这两组初始数据所包含的信息并不等价，显然似乎是第一组数据包含的信息要多一些，这是因为第一组数据所给出的长度都是关于整段基因的绝对位置，而第二组全部都是相对位置。2标准化SPDP问题的建立我们就可以建立标准化的SPDP问题。建立过程如下：第一步：利用相邻重值等效方法去除由于相邻对称的位点所确定的基因片段，调整两组数据b与c的值。第二步：首元素定理确定首元素，除去b中的首元素元与c中的对应元。第三步：利用尾元素定理与尾元素约束定理确定尾元素的可能值。并在计算中对每个有可能的尾元素进行循环，当确定其中一个可能值作为尾元素时，去除b中的尾元素元与c中的对应元。第四步：利用首尾排序定理，并将前s-1个片段看为等效首元素1sb（尾元素为sb）。这里要注意：若发现前s-1个片段中存在一个片段的长不合条件符合条件输出答案用c检验组合b图41sb1sb2sblsbmsb1lsb2lsb…………图5第6页共12页度在c中没有对应相等的值时，说明所选的尾元素并非真正的尾元素，此时返回第二步。经过上述四步处理后，SPDP的原模型已被标准化。对此时的第一组数据b重新按递增排序，并重新给予脚标，将重值赋予同样的脚标。这样就可以得到新的221Lbbbl，并记录有重值的b，仍用{ikb}这样一组数来表示。由定理三说明中的分析知道b若有重值最多只有两个元素等相等。而对于第二组数据c也同样重新赋予脚标并排序得到mccc21，并用mpppp321,,记录每一个c值重复的个数。通过上面五步的操作，我们得到标准化的SPDP问题。为了保持定理的习惯，以及后面算法设计的方便。我们对于第一组数据b不去处首尾元素，则1b为首元素，2b为尾元素，b数据满足221Lbbbl.而在c数据中我们却已经把首尾元素对应相等的值已经去除。则对于标准化问题，我们要做的事情就是要确定lbbb43，的状态组合（判定每个ib属于前半段还是后半段）。而我们的数据结构与算法就需要针对这样的标准SPDP问题进行选取与设计。对SPDP算法进行进一步的优化，建立b-b表与b-c表我们建立二叉树数据结构的思想来源于数学模型建立的立足点是通过对第一组数据b进行组合，而拿第二组数据c来进行检验。不论是最初的穷举法还是二叉树数据结构的算法都体现了第一组数据与第二组数据这样的一种关系。然而这样的关系并非完美，因为尽管c数据比b数据包含的信息要少，但对b进行组合的时候，数据c仍然是非常重要的一个约束，并且时刻的在约束着b的每一步组合。基于这样的想法，我们希望在二叉树的结点计算时可以加入c对b的约束。我们在SPDP的标准问题中建立了b-b表与b-c表。首先我们建立b-b表。在二叉树数据结构算法中，我们每步对结点树枝的是否存在的判断都是通过两个b数的差jibb是否在这个结点中数据c（可以将它看作一个集合）中。因此判断jibb是否等于kc至关重要。由此，我们就对数据b的所有元素两两作差，建立b-b表。我们可以让横坐标表示被减数ib的脚标i,第7页共12页而纵坐标表示减数j，（ji）。这里需要说明的是在这个表里我们不需要计算12bb的值，因为它们是首尾元素并且在异侧。则每个点（i,j）就表示了两个b数的差是否满足jibb=kc，如果等式jibb=kc成立，则在（i,j）位置记k，否则记0。这样我们就生成了b-b表。而我们进一步分析一下jibbkc的情况，如果c数据中最大的为mc,我们可以看到，当我们每次固定j而对i从小到大依次搜索的时候，一旦从某个b开始其差值比mc还要大的时候，之后的差值就一定也比mc大。我们在这里对这种情况加以记录，若jibbmc，则在（i,j）的位置记为-1，这样区分的好处在后面的算法里可以体现。那么，二叉树结构中每步jibb=kc的判断就转变成为判断b-b表（i,j）位置上的值。b-b表是等式jibb=kc中i与j之间的关系，而下面我们建立的b-c表是j与k之间的关系。基本b-c表，横坐标为c的脚标k，而纵坐标是被减数jb的脚标j。如果jibb=kc，那么在（k,j）的位置记i，若jibbkc，则在（k,j）的位置记0。这样，这张b-c表就有了它自身的含义，它表示着对于每一个kc，有可能组合出这个kc的两个b数的差的所有可能情况。这里就有一个非常重要的约束，对于每一个kc，两个b数相减可以等于kc的所有的组合的个数kn与数据c中kc的个数kp满足knkp+1。这里要注意，kp之所以要加1是因为“中间元素”并非为两个b值相减而得到的，所以有可能在这里kc的个数kp比kn可以小1。但一旦在kc出现了这种情况，在别的c数据的列中就不能出现这种情况，即对于其它的c数据要求np。倘若出现了与约束相矛盾的情况时，再往后计算肯定得不到合理解了，需要换下一个可能的尾元素。第8页共12页b50000b45000b30455b20304b13003c1c2c3c4p1p2p3p4表3.b-c初始表…..得到了b-c表的这个约束后，下一步需要解决的就是如何在二叉树建立的过程中在不改变开始时候做的b-c表而对每个结点的kn进行计算并与该节点的kp相比较。首先，我们发现kp在每次节点中的变化是因为每次计算需要除去c数据中的一个值而导致kp的变化。对于每个节点，都需要记录所有的kp的值。然而，对于kn,我们并不需要每次都改变b-c表，而是直接从b-c表中计算出当前情况kn的值。这样，我们就需要对b-c表进行一个补充。对于每一列kc,我们又增加了两个子列，一列为状态数（J函数），另一列为排序（R函数）。我们现在来考察二叉树在建立过程中其中的一个节点的情况，如表4所示，假设该J函数被减数R函数J函数被减数R函数J函数被减数R函数J函数被减数R函数b5002002001003b4152002001003b3001142151153b2001131000142b1131000000131表4.完整b-c表c1c2c3c4节点的前半段已经考虑到ib，后半段已经考虑到jb。当前需要考虑b到底属于前半段还是属于后半段。倘若b被放到了前半段，生成该节点的左树枝及其节点，我们发现，对于这个新生成的节点，对于任何，b-ib在这里已经是不可能的组合，同理我们发现，纵坐标比i小的与i,j之间的那些可能与c相等的b的差值的组合在这里已经没有意义了，需要在所有初始时b的差的组合总数中减去