《基因片段重构模型》由会员分享，可在线阅读，更多相关《基因片段重构模型（23页珍藏版）》请在金锄头文库上搜索。
1、基因片段重构模型潘强江帆童大力基因片段重构模型摘要：绘制DNA限制性图谱是进行遗传分析的重要手段，简化的部分消化法（SPDP） 是应用广泛的一种方法，该法要求对打乱的DNA片段进行重新排序。我们针对提供的 各片段生物信息建立了 0-1 方程模型从而解决了基因片段的重构问题。在第一问中我们 利用限制性位点必定落在DNA两半段中的一半段中的情况，运用0-1特性对该情况进 行表示，再根据题设和推理分析建立方程组。再利用 Matlab7.1 编程求解，对实例一和 实例二分别给出了一组和多组解，经效果考评较好；同时，在既得优化解的基础上，我 们运用程序模拟讨论了误差的影响情况，得出结论：1、某一限制性位
2、点的误差不影响 其他限制性位点；2、大部分的位点误差则可能导致序列重构失败。本模型运用的数学 思想具有创新性，在极大程度上简化了运算难度，并可推广至园林布局，路线设计和管 道拼接等诸多领域，发挥更广泛的社会效应。关键词：鸟枪法 DNA 序列重构 01 规划 MATELAB7.1一、问题重述绘制 DNA 限制性图谱是进行遗传生物分析的重要手段，但鉴于分子碱基对数目过 多和分子量过大，在科学实验中需要运用生化技术将DNA酶切成小分子片段。具体地, 本题提供了 PDP 方法和简化 PDP 方法，根据酶切位点的不同和各片段基本的生物信息 进行排列组合，以获得整条DNA分子的相关信息。我们面临的问题：1
3、、结合数学思想求解 DNA 分子排列组合的普遍算法，评估效率和效果，并对题 中所给两个实例进行验证；2、讨论片段长度误差对测量算法的影响范围以及其妨碍限制性图谱正常构建的临 界值。二、基本假设1、所给数据真实可靠；2、仅从数学方面考虑此问题，既不考虑其生物学影响；3、排列顺序相反的视为同一种情况；4、在酶作用时无剪切丢失片断；5、在未作特殊规定时不考虑测量片断时的长度误差；6、当考虑测量长度误差时，仅考虑两组数据之间的相对误差三、符号规定A 为第一组数据的集合；B 为第二组数据的集合；M 为 DNA 分子的总长度；I为DNA分子中的第i个剪切点；iP、Q分别为DNA分子两端端点；a为第i个剪切
4、点到DNA分子两端点距离中的最近距离，aa为对应的剪切点到另ii一端点的距离；C 为靠近 P 端的剪切点到 P 点的距离的集合， CC 为靠近 Q 端的剪切点到 Q 点的 距离的集合；l 为靠近 P 端点的半段 DNA 上各片段的长度， ll 为靠近 Q 端点的半段 DNA 上各 ii片段的长度；S 为剪切酶在各个剪切位点同时作用时所得到的剪切片断长度的集合。四、问题分析本题为一道与生物学知识密切相关的建模问题，通过查阅资料可知，这种测序方法 就是美国塞莱拉遗传公司创始人克雷格文特尔发明的“鸟枪法”1。从全文意思，所给 出的数据，以及最后需求解的问题来看，可以运用排列组合的方法进行求解。我们需
5、要 寻找第二组数据所代表的 DNA 各片段的正确序列，使当 DNA 分子分别在各个限制性 位点处被切开所得到的数据与第一组数据相符，既利用第二组数据所代表的 DNA 各片 段进行排序，使当重组DNA分子分别在各个限制性位点处被切开所得到的数据与第一 组数据相符，则说明本次排序具有一定意义，既可能为原 DNA 排列顺序。问题一由于本问实例一与实例二解题思路具有高度一致性，所以现在就以实例一为例进行 分析。由于给出了具体数据，分析数据可知，该限制酶在本段DNA分子中总共有4个 酶切位点，且单一位点进行切割时得到相应的第一组数据既（2， 14， 8， 8， 7， 9， 3， 13），而完全剪切后得到
6、第二组 DNA 片断数据为（1、2、3、4、6）。由题意可知，第 一组数据中的各个数均可由第二组数据中的某一个或几个数相加得到。在第一组数据中 最小的剪切片断长度为 2，第二组数据中只有2能与之对应，所以其对应的酶切点应为 最靠近端点的一个酶切点；而第一组数据中的数字 3在第二组数据中则可以对应（1+2）、 3，再大一点的数对应的相应组合数会更多，所以由简单的推理基本不能解决此问题。再进一步分析，若我们能将第二组数据进行排序（运用换位法 2），若从一端按各 个酶切点分割能得出第一组数据中的每个数字，则说明排列的顺序是正确的。所以我们 可以根据所给的数据运用容斥原理3的知识列出相应的限制条件（具
7、体见模型建立）， 然后根据题设条件逐个搜索，本过程可运用 MATELAB7.1 编程实现。但这种方法在数 据量增多时会明显影响运算，所以我们又提出了第三种方法。因为在第一组数据中有两个数表示的是同一个意思，如 2 和 14， 3 和 13，它们仅 表示两个剪切位点，所以我们将第一组数据分为两组数据，既（2， 3， 7， 8）和（14， 13， 9， 8）。仅运用其中一组数据，如我们选取（2， 3， 7， 8），此组数据表示每个剪切 位点与 DNA 分子两个端点的距离中的最近距离。所以我们仅需用这组数据排序将每个 剪切位点表示出来，若同时在各个剪切位点进行剪切后所分得的 DNA 片断长度能与第
8、二组数据（1、2、3、4、6）相同，则说明排序有意义。在此我们在第二种方法编程的 基础上运用 01 规划4对剪切点位置进行标定，最终得出结果。具体实施见模型建立 与求解。问题二 对于此问，因为要考虑实验中测量长度的误差，若对每一个片断的绝对长度进行精 确考虑，则工作量相当大，而且没有普遍意义。在真正实验中，酶解后的片断都是经过 统一测量，既测量时测量工具，测量环境以及一切外部条件都相同，所以其误差在同一 组数据中具有普遍意义和具有一定的相似性，既在考虑误差时，我们就只考虑两组数据 中的相对误差即可（具体见模型建立及求解问题二）。五、模型建立及求解问题一首先我们针对一般情况，建立一个通用的 0-
9、1 模型，然后再应用此模型解决实例 1 和实例 2。（一）、01 方程模型的建立设： DNA 在各个限制性位点处被切开所测量得的数据（第一组数据）为：A = a ,aa ,a ,aa ,a ,aa ,a ,aa ,其中a ,aa为同次切割所得的两个数据。1 1 2 2 3 3 n n i iDNA 各限制性位点（包括 DNA 两端点）间的片段长度（第二组数据）为：B = b , b , b ,b 。123n+1M = a + a a = b + b + +ii 123对第一组数据进得处理得：aA = aanaaaa23其中，a至a各数均小于或等于M，且a + aa = M，所以只由a就可体现第
10、一组数据1 n2i ii的意思，即 A 可表示为：A = a1a , a , ,a23na , a , a，,a各数均为各自对应的限制性位点到最近端点的距离，如图1。那么各限制123n性位点Ii要么在靠近P端点的半段DNA上，要么在靠近Q端点的半段DNA上。12345Pn-1n图1中各数的取值只能为 0 或 1。得到数列C = a - x , a - x , a - x ,a - x 和112233n nCC=a - (1 - x ), a - (1 - x ), a - (1 - x ),，a - (1 - x )。112233nn若x = 1则表示点Ii在靠近P端点的半段DNA 上,若x
11、= 0则表示点Ii在靠近Q端点的ii 半段 DNA 上。对C和CC数列中的各数进行从小到大的排序，得到新的数列：CC = cc , cc , cc ,cc 。123n其中 c , c , c ,c 为 a - x, a - x , a - x ,a - x 的升序排列，cc , cc , cc ,cc 为123n 112233n n123na - (1 - x ), a - (1 - x ), a - (1 - x ),a - (1 - x )的升序排列112233nn那么该DNA上各限制性位点(包括DNA两端点)间的片段长度可作如下表示: 在靠近P端点的半段DNA上各片段的长度为：1、2、i
12、 = 1l = ci 1 ；1 i n l = c -cii i -1在靠近Q端点的半段DNA上各片段的长度为:3、i = 1 1 i n在最中间的片段长度为：ll = cci1；ll = cc - ciii -1-(c + cc )。nn其中数值为 0 处表示没有片段。用所得片段长度建立一个数列S = l , l , l , ,l ,ll , ll , ll , ,ll , M - (c + cc )，123n 123nnn再对S数列中的元素进行从小到大的排序得：S = s , s , s ,s 。1232n+1因为点Ii要么在靠近P端点的半段DNA上，要么在靠近Q端点的半段DNA上即xi
13、等于0或1,所以C和CC中的2n个数中有n个数等于0,所以S中有n个数等于0。将 数列S中的前n个数去掉，得到表示DNA上各限制性位点(包括DNA两端点)间片段 的长度的数列：SS = s , s , s , , s 。 n+1 n+2 n+3将数列 B 中的元素进行从小到大的排序，得到：B = bb , bb , bb , bb123。+1bb ,bb ,bb , bb为 b ,b ,b , b 的升序排列。12 3n+11 2 3n+1所以SS和B是完全等同的数列，有SS = B，故可建立方程组如下:s = bbn +11s = bbn + 22 s = bbn + 33s = bb2 n
14、 +1n +1由MATLAB7.1可对x ,x ,x，x进行求解，从而得出各限制性位点在原DNA上 123 n的位置，进而推算出原 DNA 序列顺序。二）、实例求解实例 1 求解第一组数据为 2， 3， 7， 8， 8， 9， 13， 14，则：A = 2，3，7，8 ；第二组数据为 2， 1， 4， 3， 6，则：B = 2，1， 4， 3，6 ；DNA 总长度：M =+ +=由 MATLAB7.1 解得（见附录 程序一）：-10001001x =011001118，9， 11， 12， 12， 13， 14，还原得到第二组数据所代表的片段的排列顺序为：26143261433416234162若 P、Q 两端无顺序区别，则有 1 组解：26143（或 3416若 P 、 Q 两端有序区别，则有
