2022年第十一届数学建模国际赛小美赛
B题 序列的遗传过程
原题再现：
序列同源性是指DNA、RNA或蛋白质序列之间的生物同源性，根据生命进化史中的共同祖先定义[1]。DNA、RNA或蛋白质之间的同源性通常根据它们的核苷酸或氨基酸序列相似性来推断。显著的相似性是两个序列通过共同祖先序列的进化变化而相互关联的有力证据[2]。
考虑RNA序列的遗传过程，其中核苷酸碱基的突变是偶然发生的。为简单起见，我们假设序列突变是由于单个碱基的改变（转换或转换）、插入和删除引起的。因此，我们可以通过突变点的数量来度量两个序列之间的距离。多个碱基序列紧密结合可以形成一个家族，它们被认为是同源的。
您的团队被要求开发一个合理的数学模型来完成以下问题。
1、请设计一种算法，快速测量两个足够长（>103个碱基）的碱基序列之间的距离。
2、请可靠地评估算法的复杂度和准确性，并设计合适的例子加以说明。
3、如果一个家族中的多个碱基序列是由一个共同的祖先序列进化而来，设计一个高效的算法来确定祖先序列，并映射系谱树。
整体求解过程概述(摘要)
随着现代基因组学的发展，越来越多的基因序列被破译出来。基于如此庞大的基因数据库，高效地实现基因序列比对具有重要意义。碱基序列间的相似性不仅可用于基因性状分析，还可用于确定基因同源性和进化过程。
为了量化基因同源性，我们提供了基因距离和相似性的明确定义。两个碱基序列之间的基因距离可以用将序列Sm转换为另一个序列Sn的代价来表示，在转换过程中，只允许使用一系列合格的编辑手段，如插入和替换字符。相似性是指两个序列之间相等的碱基数目。在遗传距离和相似性的计算中，基因比对是一个整体。
基因比对的关键是找出碱基序列之间如何合理匹配，以减少单个碱基变异对整体比对的影响。将基因序列视为一个由a、G、T、C四个字符组成的字符串，其两两匹配问题等价于经典的LCS（最长公共子序列）问题，即通过增加空格使两个字符串对应位置的相等字符数最大化。
由于单个字符的编辑操作受到限制，因此可以列出每个匹配的状态转移方程，然后使用动态规划算法：Needleman-Wunsch（NW）算法找到最佳匹配。经过结构分析，该算法的时间复杂度和空间复杂度均为O（mn）。通过和现有序列匹配工具的比较，表明该算法具有高效性、准确性和适用性，匹配度为86.71%。
根据基因距离，我们可以在一组同源基因中反转共同的祖先序列，并绘制家谱树。对于系谱树，我们参考系统发育树的生成，并应用两种算法来重建一组基因之间的进化过程。邻域连接法（NJ）和算术平均无权对群法（UPGMA）采用不同的聚类原则，可以构造两个不同的系谱树。将系统发育树与序列比对算法相结合，有效地得到了原始序列。
为了验证系谱树的准确性，我们还设计了一个自顶向下的生成程序来模拟基因进化过程。结果表明，回溯得到的祖先序列与生成序列的起始点具有很高的相似性，证明了该算法的准确性和实用性。
模型假设：
为了简化问题，我们做了以下假设：
•1.有限的基因突变
我们假设序列突变只发生在单个碱基发生改变、插入和缺失的情况下。
•2.所研究的序列对一般都具有全局最优比对，基因序列比对大致可分为全局比对和局部比对两类。为了简化情况，
•3.尽管正、副同系物是同系物的两个重要概念，但它们之间的区别是可以忽略的，难以量化和区分。因此，我们忽略了这两个亚类之间的差异，只关注同源基因的遗传距离。
•4.模拟的基因变异率高于实际的基因变异率，实际的基因变异率很低，约为50%。然而，在模拟程序中，我们假设每个变异率都略高于实际值，以使比较更加显著。
问题重述：
为了更有效地解决问题，我们将课题的要求归纳为以下具体问题，并对如何回答这些问题进行了深入分析。
•问题1：设计一种有效的算法来测量两个碱基序列之间的遗传距离。
计算基因距离有两个关键点：
1、确定基因距离的定量表示
2、设计一种高效的算法实现两个字符串序列的对齐
•问题2：评估算法的复杂性和准确性。
对于复杂性，需要进行时间和空间复杂性分析；在准确性方面，我们设计了几个特殊的测试样本，以验证算法逻辑的严密性。
•问题3：设计一种有效的算法来确定多个同源碱基序列的祖先序列。
基于上述基因距离的确定，我们可以得到一组碱基序列中任意两个样本之间的相似性。通过不断寻找相似度最大的样本，并将它们合并得到它们的直系祖先，我们可以自下而上构造一棵系谱树。
与问题2类似，我们可以生成一系列具有已知遗传关系的序列来检验算法的准确性。
模型的建立与求解整体论文缩略图
全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
部分程序代码：(代码和文档not free)
1 import sys
2 import time
3 import platform
4
5 def theta(a, b):
6 if a != b: # gap or mismatch
7 return −1
8 if a == b: # match
9 return 1
10 if a == ’−’ or b == ’−’:
11 return −1
12
13 def make_score_matrix(seq1, seq2):
14
15 seq1 = ’−’ + seq1
16 seq2 = ’−’ + seq2
17 score_mat = {}
18 trace_mat = {}
19
20 for i,p in enumerate(seq1):
21 score_mat[i] = {}
22 trace_mat[i] = {}
23 for j,q in enumerate(seq2):
24 if i == 0:
25 # first row, gap in seq1
26 score_mat[i][j] = −j
27 trace_mat[i][j] = 1
28 continue
29 if j == 0:
30 # first column, gap in seq2
31 score_mat[i][j] = −i
32 trace_mat[i][j] = 2
33 continue
34 ul = score_mat[i−1][j−1] + theta(p, q)
35 # from up−left, mark 0
36 l = score_mat[i][j−1] + theta(’−’, q)
37 # from left, mark 1, gap in seq1
38 u = score_mat[i−1][j] + theta(p, ’−’)
39 # from up, mark 2, gap in seq2
40 picked = max([ul,l,u])
41 score_mat[i][j] = picked
42 trace_mat[i][j] = [ul, l, u].index(picked)
43 # record which direction
44 print("SameNum:",score_mat[i][j])
45 return score_mat, trace_mat
46
47 def traceback(seq1, seq2, trace_mat):
48
49 seq1, seq2 = ’−’ + seq1, ’−’ + seq2
50 i, j = len(seq1) − 1, len(seq2) − 1
51 path_code = ’’
52 while i>0 or j > 0:
53 direction = trace_mat[i][j]
54 if direction == 0:
55 # from up−left direction
56 i = i−1
57 j = j−1
58 path_code = ’0’ + path_code
59 elif direction == 1:
60 # from left
61 j = j−1
62 path_code = ’1’ + path_code
63 elif direction == 2:
64 # from up
65 i = i−1
66 path_code = ’2’ + path_code
67 return path_code
68
69 def print_m(seq1, seq2, m):
70 seq1 = ’−’ + seq1; seq2 = ’−’ + seq2
71 print()
72 print(’ ’.join([’%3s’ % i for i in ’ ’+seq2]))
73 for i, p in enumerate(seq1):
74 line = [p] + [m[i][j] for j in range(len(seq2))]
75 print(’ ’.join([’%3s’ % i for i in line]))
76 print()
77 return
78
79 def pretty_print_align(seq1, seq2, path_code):
80 align1 = ’’
81 middle = ’’
82 align2 = ’’
83 n=0
84 for p in path_code:
85 n=n+1
86 if p == ’0’:
87 align1 = align1 + seq1[0]
88 align2 = align2 + seq2[0]
89 if seq1[0] == seq2[0]:
90 middle = middle + ’|’
91 else:
92 middle = middle + ’ ’
93 seq1 = seq1[1:]
94 seq2 = seq2[1:]
95 elif p == ’1’:
96 align1 = align1 + ’−’
97 align2 = align2 + seq2[0]
98 middle = middle + ’ ’
99 seq2 = seq2[1:]
100 elif p == ’2’:
101 align1 = align1 + seq1[0]
102 align2 = align2 + ’−’
103 middle = middle + ’ ’
104 seq1 = seq1[1:]
105
106 if n==50:
107 print(’EMBOSS_001:’ + align1)
108 print(’EMBOSS_002:’ + align2+ ’\n’)
109 n=0
110 align1 = ’’
111 align2 = ’’
112 return
113
114 def usage():
115 print(’Usage:\n\t python nwAligner.py seq1 seq2\n’)
116 return
117
118 def main():
119 with open(’gene1.txt’,’r’,encoding=’utf−8’) as f1:
120 seq1 = f1.read()
121 with open(’gene2.txt’,’r’,encoding=’utf−8’) as f2:
122 seq2 = f2.read()
123 #
124 # print(’1: %s’ % seq1)
125 # print(’2: %s’ % seq2)
126
127 score_mat, trace_mat = make_score_matrix(seq1, seq2)
128 # print_m(seq1, seq2, score_mat)
129 # print_m(seq1, seq2, trace_mat)
130
131 path_code = traceback(seq1, seq2, trace_mat)
132 pretty_print_align(seq1, seq2, path_code)
133 # print(’ ’+path_code)
134
135 if __name__ == ’__main__’:
136 print(’:’, platform.system())
137 T1 = time.perf_counter()
138 main()
139 T2 =time.perf_counter()
140 print(’:%s’ % ((T2 − T1)*1000))
%−−−−−−−−−−−−−−− test1−−−−−−−−−−
2 % Runs example for UPGMA and NJ
3
4 clc
5 clear all
6
7 data = {’Anolis’ ’ATGACAATTACACGCAAATCCCACCCAATTTTC
8 AAAATTATTAACGACTCCTTTATTGAT’;
9 ’Basili’ ’ATGACAATCCTACGAAAATCCCACCC
10 AATCCTTAAAATAATCAACTCTTCATTCATCGAC’;
11 ’Chalar’ ’ATGACAATCATCCGAAAAACACACCC
12 AATTTTCAAAATTGTAAACGACTCATTCATTGAC’;
13 ’Gambel’ ’ATGACAATCACACGAAAATCCCACCCG
14 ATCATCAAAATCGTAAACAACTCATTTATTGAC’;
15 ’Leioce’ ’ATGACAATCACACGAAAAACTCACCCA
16 CTATTTAAAATCATCAATAACTCCTTTATTGAC’;
17 };
18 for ind = 1:length(data)
19 f(ind).Header = data{ind,1};
20 f(ind).Sequence = data{ind,2};
21 end
22
23 % UPGMA
24 distances = seqpdist(f,’Method’,’Jukes−Cantor’,’Alpha’,’DNA’);
25 UPGMAtree = seqlinkage(distances,’UPGMA’,f);
26 h = plot(UPGMAtree, ’orient’, ’top’);
27 title(’UPGMA Distance Tree of Iguanas
28 using Jukes−Cantor model’);
29 ylabel(’Evolutionary distance’)
30
31
32 % NJ
33 NJtree = seqneighjoin(distances,’equivar’,f);
34 h = plot(NJtree, ’orient’, ’top’);
35 title(’Neighbor−Joining Distance Tree of Iguanas using
36 Jukes−Cantor model’);
37 ylabel(’Evolutionary distance’)
38
39 %−−−−−−−−−−−−−−−− test2 −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
40 % This test runs Branch and Bound and Exhaustive Search
41
42 clear all
43 clc
44 data_iguana = { ’Anolis’ ’ATGACAATTACACGCAAATCCCACCCAATTTT
45 CAAAATTATTAACGACTCCTTTATTGAT’;
46 ’Basili’ ’ATGACAATCCTACGAAAAT
47 CCCACCCAATCCTTAAAATAATCAACTCTTCATTCATCGAC’;
48 ’Chalar’ ’ATGACAATCATCCGAAAAA
49 CACACCCAATTTTCAAAATTGTAAACGACTCATTCATTGAC’;
50 ’Gambel’ ’ATGACAATCACACGAAAATCCC
51 ACCCGATCATCAAAATCGTAAACAACTCATTTATTGAC’;
52 ’Leioce’ ’ATGACAATCACACGAAAAACTCA
53 CCCACTATTTAAAATCATCAATAACTCCTTTATTGAC’;
54 ’Leioce1’ ’ATGACAATCACACGAAAAACTCAC
55 CCACTATTTAAAATCATCAATAACTCCTTTATTGAC’;
56 ’Leioce2’ ’ATGACAATCACACGAAATACT
57 CACCCACTATTTAAAATCATCAATAACTCCTTTATTGAC’;
58 ’222222’ ’ATGACAATCACACGAAATACTCA
59 CCCACTATTTAAAATCATCAATAACTCCTTTATTGAC’;
60 };
61
62 %Create a matrix with al sites with usefull information
63 [row, col] = size(data_iguana);
64 for i = 1:row
65 temp = data_iguana{i, 2};
66 matrix{i, :} = temp;
67 names = data_iguana{i, 1};
68 name_matrix{i, :} = names;
69 end
70
71 for i = 1:row
72 data(i, :) = matrix{i};
73 end
74
75 set_of_seq = non_inf_sites(data, 3);
76 %Search using improved Branch and Bound
77 tic
78 [optimal_score, optimal_model] = BrB(set_of_seq, name_matrix);
79 toc
80
81
82 %% Search using Exhaustive Search
83 tic
84 [optimal_score1, optimal_model1] = ExhaustiveSearch(set_of_seq,
85 name_matrix);
86 toc