您的位置：软件研发->动态编程和基因序列比对

动态编程和基因序列比对2008-04-22 来自：villa123  [收藏到我的网摘]

Paul Reiners (reiners@us.ibm.com), 软件工程师, IBM　

2008 年 4 月 17 日

分子生物学越来越多地将计算机科学算法作为研究工具。本文将介绍生物信息学 — 用计算机解决生物学问题。学习动态编程 的基本原理，这是一种高级的计算技术，您将发现它在许多编程项目中都很有用。
基因组数据库保存了海量的原始数据。人类基因本身就有接近 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 个斐波纳契数：

推荐人评论

分子生物学越来越多地将计算机科学算法作为研究工具。本文将介绍生物信息学 — 用计算机解决生物学问题。学习动态编程 的基本原理，这是一种高级的计算技术，您将发现它在许多编程项目中都很有用。

用户评论

正在载入评论列表...