【Algorithm】基因序列比较

基因序列比较

1.1题目描述

设计算法，计算两给定基因序列的相似程度
人类基因由4种核苷酸，分别用字母ACTG表示。要求编写一个程序，按以下规则比较两个基因序列并确定它们的相似程度。即给出两个基因序列AGTGATG和GTTAG，它们有多相似呢？测量两个基因相似度的一种方法称为对齐。使用对齐方法可以在基因的适当位置加入空格，让两个基因的长度相等，然后根据基因的分值矩阵计算分数。

例：比较AGTGATG与GTTAG
第一种对齐方案为：
首先可以给AGTGATG插入一个空格得：AGTGAT-G
GTTAG插入3个空格即得：-GT–TAG
上面的匹配分值为:-3+5+5+(-2)+(-3)+5+(-3)+5=9.
第二种对齐方案为：
AGTGATG
-GTTA-G
得到的分值为：(-3)+5+5+(-2)+5+(-1)+5=14.
当然还有其它对齐方式，但以上对齐方式是最优的，所以两个基因的相似度就为14。

1.2问题分析与解决思路

1.2.1问题分析

问题是判断基因序列的相似度，根据题目的对齐方法，设两条基因序列分别为长度为m的X序列和长度为n的Y序列，可以理解为要找一条由坐标（0,0）到坐标（m-1，n-1ÿ

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！