数学建模社区-数学中国

标题: 多重序列比对的数学模型与算法 [打印本页]
作者: ljh200906    时间: 2009-7-31 17:54
标题: 多重序列比对的数学模型与算法
多重序列比对的数学模型与算法自美国提出组织的人类基因组计划（Human Genome Proreet）简称为HGP以来，美国每年拔出相当大的经费支持，日本、法国、英国、德国等纷纷响应，它们的工作使新的交叉学科生物信息论得以诞生和发展，生物信息论是用数理和信息科学的观点、理论和方法去研究生命现象，组织和分析呈指数增长的生物学数据。生物信息学是一门综合学科，是计算机科学、数学、物理、生物学的结合。生物信息学的基础是各种数据库的建立和分析工具的发展。目前，生物学数据库已达500个以上，共有四大类：基因组数据库，核酸和蛋白质一级结构数据库、生物大分子三维空间结构数据库及其以她们为基础构建的二级数据库。生物信息学主要研究基因组测序及其信息分析、生物大分子的结构与功能预测及其模拟和药物设计、大规模基因表达数据的分析与基因芯片设计，以及基因与蛋白质相互作用网络等四方面的问题。" w' G: ]$ a, p- E5 S4 y4 C# [
多重序列比对是计算分子生物学中最重要的运算。多重序列比对的基本问题就是找出适当安排删减与插入尽量少的空格，使得两个序列达到最大程度的一致的方案。比如给出下列三个序列：
1 H, }7 a( w( L9 u5 t                AC_G
& n6 K8 w/ k$ |( ?0 ^5 }3 I3 X                AGTCC     (1)
" [! r; a9 j% x! W                ACT
: O) @: g7 t- m; E

4 e3 a5 J' G* X4 \. b5 o/ g
, ^" M# U' P7 C' K' P. ]
我们适当安排删减与插入空格得到：: |6 v5 G$ b! V; p9 C$ e
                ACG___5 @6 ^6 a; F, Q- r' s2 v$ J
                A_GTCC    (2)" n2 v; i7 t, q& d5 H9 w3 u
                AC_T__& o$ @8 v$ h: X5 w1 I: P
; I- |) N6 L& Q: k' X
（2）就是多重序列的一个比对。
: B/ Q% Z0 o; Q1 {/ d+ \% g! B" d局部分段比对是其中更为常见的运算。上世纪80年代，Smith-Waterman提出了两个序列的局部比对的明确的模型。1998—1999年，相继出现利用k-tuple的快速容错分段比对搜索法。2002年开始出现对完整基因组及其异常基因的比较研究以及多重序列比对问题的研究，2003年刘军Mayetri Gupta和刘军得到Motif的搜索算法。: \& x4 S$ J9 m/ o+ F0 z( e9 m
人类基因组计划后，目前已经进入后基因时代，主要就是对人类基因组计划实施得到的基本数据库进行信息分析、加工和利用，提取有用信息，用来研究生命现象中的重大问题。多重序列比对问题是生物信息学的基本问题，多重序列比对技术也是生物信息学的基本工具，有着十分广泛的应用，比如基因是否为同一个家族，癌症患者的基因与正常时的基因比对分析等等。因此，请您们就基因的多重序列比对，设计合理的衡量比对好坏的定量描述模型，建立多重序列比对的基本问题的数学模型，并设计一种求解的算法。最后就附录一中的12个序列，请您们利用你们得到的模型与算法，给出使序列有最大相似程度的比对。$ ~: T# d, ?8 a% X
附录一：' O7 x& a) {" B0 V1 R
CATTTCTTTTTAGGGATTTTAAAAGTTGTCTTTTCTT8 J/ I7 [4 G: z; ~' z1 q
CATTTCTTTTTAAGGTTTTAAAAATTGTCTTTTTT
: a! r1 m2 u2 N( G! t; _: N5 ?CATTTCTTTTTAAGGGTTTTAAAAATTGTCTTTTCTT& _2 p8 ^+ [3 U9 L! Q& F0 \* l
CATTTTTTCTTAAGTGTTTTGGTATTTATCTTTTTCTT
& f) ?2 z; q1 n4 ]) z+ SCATTTTTGCTTATGTATTTATAGTGGGTTGTCTTTTTGACTT' r0 P$ ?. z% q+ z
CATTTCTTTTGAAGTGATTTGAGATTTATCTTTTTCTT
/ y& T, G4 m4 ^8 I6 jCATTTCTTTTTAAGGGTTTTAAAAATTGTCTTTTCTT
+ X% X8 \; o/ y3 T0 ?7 \CATTTCTTTTTATGTTGAGATATTTGTCTGTTTTCTT" p/ U  Z" y8 X# n  n7 u
CATTTTTACTATGTGTTGATTGTGGATTGTCTTTTCTT
+ f+ Q9 S( o5 _CATTTCTTTTATTGAGTGAAGAAGAGATTTTGTCTTGTTTTGAT! I; p& R7 D5 `& F: z9 P; q$ c
CATTTTTCTTAGTGTTTTGGTATTTATCTTTTTCTT4 R8 {* @2 t( `9 h/ }+ X4 e' e
CATTTCTTTTAAGGGTTTTAAAAATTGTCTTTTCTT
作者: 何挺    时间: 2009-7-31 21:12
???????????????????????????
作者: menger    时间: 2009-8-9 12:22
有没有答案啊，分享一下
作者: Bruceee    时间: 2009-8-9 18:14
论文呢？8 b+ P8 U  O; u. [" y$ ^  }
分享一下
作者: Bruceee    时间: 2009-8-9 18:15
有就传上来啊
作者: xsoul    时间: 2009-8-9 21:57
使添加的空格尽量少？
作者: Kadyniost    时间: 2009-8-9 22:36
什么东西啊。。。。。。。
作者: shuxuejianmo2    时间: 2009-8-10 14:21
哎正在做！！！！
作者: yong1362121    时间: 2009-8-10 15:57
什么东西啊。。。。。。。
作者: joycehere    时间: 2009-8-10 17:22
论文啊，想看就掏腰包啊
作者: raulliuke    时间: 2009-8-10 23:25
希望有点帮助~

超级多重基因组序列比对算法.pdf

180.99 KB, 下载次数: 0, 下载积分: 体力 -2 点

多重序列比对的蚁群算法.pdf

349.12 KB, 下载次数: 0, 下载积分: 体力 -2 点

基于免疫遗传算法的多重序列比对.pdf

219.66 KB, 下载次数: 0, 下载积分: 体力 -2 点

基于免疫遗传算法的多重序列比对.pdf

219.66 KB, 下载次数: 0, 下载积分: 体力 -2 点

基于遗传算法和蚁群算法的多重序列比对.pdf

168.85 KB, 下载次数: 0, 下载积分: 体力 -2 点

基于隐马尔可夫模型的多重序列分析.pdf

240.69 KB, 下载次数: 0, 下载积分: 体力 -2 点

一种新型求解多序列比对问题的方法.pdf

193.02 KB, 下载次数: 2, 下载积分: 体力 -2 点

基于遗传算法的一种生物序列比对方法.pdf

144.67 KB, 下载次数: 0, 下载积分: 体力 -2 点
作者: rotman173    时间: 2009-8-11 10:07
论文呢  论文呢 论文呢 论文呢 论文呢 论文呢 论文呢 论文呢 论文呢 论文呢 论文呢 论文呢 论文呢
作者: shy87814    时间: 2009-8-11 15:05
you  da an  bu  ????
作者: shy87814    时间: 2009-8-11 15:05
swfwfwv   sedfsqdv  fdsqfqs  wefqwef
作者: shy87814    时间: 2009-8-11 15:05
fqsdfdsf   sefsdfav   dgadfvadf  asdgdfgadg fdsavcva
作者: shy87814    时间: 2009-8-11 15:06
fgfbfs b  dfgdgw   sdgsfgb   gfbshgh
作者: hnbc    时间: 2009-9-10 13:21
O(∩_∩)O谢谢
作者: hnbc    时间: 2009-9-10 13:22
O(∩_∩)O谢谢
作者: zhaodonghui3939    时间: 2009-12-7 19:24
ddddddddddddddddddddddddddddddddddddddddddddddd定下



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5