男孩子怎么做网站推广,深圳龙华大浪做网站公司,设计精美的中文网站,青岛建站公司推荐2022年第十一届数学建模国际赛小美赛
B题 序列的遗传过程
原题再现#xff1a; 序列同源性是指DNA、RNA或蛋白质序列之间的生物同源性#xff0c;根据生命进化史中的共同祖先定义[1]。DNA、RNA或蛋白质之间的同源性通常根据它们的核苷酸或氨基酸序列相似性来推断。显著的相…2022年第十一届数学建模国际赛小美赛
B题 序列的遗传过程
原题再现 序列同源性是指DNA、RNA或蛋白质序列之间的生物同源性根据生命进化史中的共同祖先定义[1]。DNA、RNA或蛋白质之间的同源性通常根据它们的核苷酸或氨基酸序列相似性来推断。显著的相似性是两个序列通过共同祖先序列的进化变化而相互关联的有力证据[2]。 考虑RNA序列的遗传过程其中核苷酸碱基的突变是偶然发生的。为简单起见我们假设序列突变是由于单个碱基的改变转换或转换、插入和删除引起的。因此我们可以通过突变点的数量来度量两个序列之间的距离。多个碱基序列紧密结合可以形成一个家族它们被认为是同源的。 您的团队被要求开发一个合理的数学模型来完成以下问题。 1、请设计一种算法快速测量两个足够长103个碱基的碱基序列之间的距离。 2、请可靠地评估算法的复杂度和准确性并设计合适的例子加以说明。 3、如果一个家族中的多个碱基序列是由一个共同的祖先序列进化而来设计一个高效的算法来确定祖先序列并映射系谱树。
整体求解过程概述(摘要) 随着现代基因组学的发展越来越多的基因序列被破译出来。基于如此庞大的基因数据库高效地实现基因序列比对具有重要意义。碱基序列间的相似性不仅可用于基因性状分析还可用于确定基因同源性和进化过程。 为了量化基因同源性我们提供了基因距离和相似性的明确定义。两个碱基序列之间的基因距离可以用将序列Sm转换为另一个序列Sn的代价来表示在转换过程中只允许使用一系列合格的编辑手段如插入和替换字符。相似性是指两个序列之间相等的碱基数目。在遗传距离和相似性的计算中基因比对是一个整体。 基因比对的关键是找出碱基序列之间如何合理匹配以减少单个碱基变异对整体比对的影响。将基因序列视为一个由a、G、T、C四个字符组成的字符串其两两匹配问题等价于经典的LCS最长公共子序列问题即通过增加空格使两个字符串对应位置的相等字符数最大化。 由于单个字符的编辑操作受到限制因此可以列出每个匹配的状态转移方程然后使用动态规划算法Needleman-WunschNW算法找到最佳匹配。经过结构分析该算法的时间复杂度和空间复杂度均为Omn。通过和现有序列匹配工具的比较表明该算法具有高效性、准确性和适用性匹配度为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 i0 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 n0
84 for p in path_code:
85 nn1
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 n50:
107 print(’EMBOSS_001:’ align1)
108 print(’EMBOSS_002:’ align2 ’\n’)
109 n0
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全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
