动态编程和基因序列比对工科.docVIP

动态编程和基因序列比对 计算机科学助力分子生物学 Paul D. Reiners, 软件工程师, EMC Paul Reiners 是一位 Sun 认证的程序员和开发员。他是多个开源程序的开发人员，包括 Automatous Monk、Twisted Life 和 Leipzig。Reiners 从伊利诺斯大学 Urbana-Champaig 分校获得应用数学（计算理论）硕士学位。他目前居住在明尼苏达州，在业余时间喜欢演奏电子贝斯，带着他的宠物鼠 Fred 和 Mortimer 闲逛，以及参加 TopCoder 的比赛。 简介： 分子生物学越来越多地将计算机科学算法作为研究工具。本文将介绍 生物信息学 —用计算机解决生物学问题。学习 动态编程的基本原理，这是一种高级的计算技术，您将发现它在许多编程项目中都很有用。 标记本文！ 发布日期： 2008 年 4 月 17 日 级别： 高级 原创语言： 英文 访问情况 ： 4535 次浏览 评论： 基因组数据库保存了海量的原始数据。人类基因本身就有接近 30 亿个 DNA 碱基对。为了查遍所有数据并找到其中有意义的关系，分子生物学家们越来越依赖于高效的计算机科学字符串算法。本文将介绍三个这方面的算法，它们都利用 动态编程技术，这是解决最优化问题的一种高级的算法技术，它从下向上寻找子问题的最优解。本文将使用这些算法的 Java™实现，还将学习一个用于处理生物学数据的开源的 Java 框架。 基因和字符串算法 基因资料 —DNA 和 RNA —链是称为 核苷酸的小单元组成的序列。为了回答某些重要的研究问题，研究人员把基因串看作计算机科学的字符串 —也就是说，可以忽略基因串的物理和化学性质，而将其想像成字符的序列（虽然严格地讲，它们的化学性质通常被编码为字符串算法的参数，您将在本文看到）。 本文的示例使用 DNA，DNA 由腺嘌呤（A）、胞嘧啶（C）、胸腺嘧啶（T）和鸟嘌呤（G）组成的核苷酸双螺旋组成。DNA 的双螺旋彼此反向互补。A和 T是互补的碱基对，C和 G也是互补的碱基对。这意味着一个链中的 A与另一个链中的 T组成一对（反之亦然），一个链中的 C与另一个链中的 G组成一对（反之亦然）。所以，如果知道一个链中的 A、C、T和 G的顺序，那么就能推导出另一个链中的顺序。所以，可以将一条 DNA 链想像成由字母 A、C、G和 T组成的字符串。 回页首 动态编程 动态编程是在序列分析中经常使用的一种算法技术。在可以使用递归，但因为递归重复解决相同的子问题造成效率低下的时候，则可以采用动态编程。例如，请看斐波纳契（Fibonacci）序列：0, 1, 1, 2, 3, 5, 8, 13, ... 第一个和第二个斐波纳契数字分别定义为 0 和 1。第 n个斐波纳契数字是前两个斐波纳契数字的和。所以，可以用清单 1 中的递归函数计算第 n个斐波纳契数： 清单 1. 计算第 n个斐波纳契数的递归函数 public int fibonacci1(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return fibonacci1(n - 1) + fibonacci1(n - 2); } } 但是清单 1 的代码效率不高，因为它重复地解决相同的递归子问题。例如，考虑一下 fibonacci1(5)的计算，如图 1 所示： 图 1. 斐波纳契数的递归计算 从图 1 可以看到，fibonacci1(2)被计算了 3 次。如果从下往上计算斐波纳契数，而不是从上往下计算，效率会更高，如清单 2 所示： 清单 2. 从下往上计算斐波纳契数 public int fibonacci2(int n) { int[] table = new int[n + 1]; for (int i = 0; i table.length; i++) { if (i == 0) { table[i] = 0; } else if (i == 1) { table[i] = 1; } else { table[i] = table[i - 2] + table[i - 1]; } } return table[n]; } 清单 2 将中间结果保存在表格中，这样就能重复使用它们，而不是在抛弃之后再重复计算多次。确实，存储表格的内存使用效率较低，因为一次只使用表格中的两个