生物工程论文

您当前的位置:学术堂 > 生物学论文 > 生物工程论文 >

启发式算法在生物信息学中的运用

来源:学术堂 作者:韩老师
发布于:2015-09-11 共1997字

  引言
  
  生物信息学作为一门新兴的交叉学科,它涵盖了计算机科学、生物学以及统计学等不同的学科。它的主要研究内容是通过应用计算机对各种生物数据信息进行检索、分析以及储存。在生物信息学中,它的各种组合问题都具有数量繁多、计算量大的鲜明特征,为了能有效地解决各类组合难问题,就必须不断提高计算的处理速度,创新计算机算法,保证各算法和程序的高效性。

  1 在生物信息学中普遍被应用的计算机算法

  在生物信息学中那些常见 NP-难的组合优化问题可以分为以下几个:群体单体型检测问题、个体单体型检测问题、多元聚合酶链反应引物集设计问题、标签 SNPs 选择问题、序列比对问题以及基因芯片的探针设计问题[1].这些问题都具有大量的信息数据,对于计算机的处理速度要求偏高。所以,必须不断优化计算机算法,对计算机算法在生物信息学中的应用展开分析和研究。通常来说,生物信息学中组合优化问题采用的计算机算法主要包括以下几种:近似算法、精确算法、启发式算法以及参数化算法等。采用近似算法通常可以得到较为满意的时间复杂度。精确算法则是生物信息学中遇到难度大组合问题的首要选择,然而它具备偏高的时间复杂度[2].启发式算法相对于传统的计算机算法,前者获得解的收敛速度会快很多。

  参数化算法通过从组合问题的参数特性研究分析入手,建立出多维的数学模型,从而有效地解决问题。

  2 启发式算法在生物信息学中的应用

  启发式算法通常被普遍应用于较大规模生物信息学的组合问题中,启发式算法具体包括了以下几种不同的算法:粒子群优化算法、神经网络算法、遗传算法、混沌免疫进化算法、模拟退火算法。

  粒子群优化算法又可以称为微粒群算法或者微粒群优化算法,它是通过模拟鸟群寻食行为而不断发展起来的一种基于群体合作的随机搜索的优化算法。通常情况下,可以将它归类为群集智能的一种,被纳入了多主体优化系统。粒子群优化算法的主要发明者为Kennedy 教授和 Eberhart 教授。在解决组合优化问题过程中,粒子群优化算法通过将问题的每一个解相对应的找出空间中某只鸟的位置,将空间中所有的鸟统称为粒子,每一个粒子的飞行都通过队员的飞行经验以及自身的飞行经验进行适当的调整。当某个粒子在实际的飞行过程中遇到最佳的飞行位置,这个就是粒子的最优解,也就是个体的极值。而如果是整个集体的最优解,也就是群体的极值,它为每个粒子所遇到过的最佳位置总和。在实际的算法操作过程中,粒子是否处于较优的位置需要通过优化函数决定的适应度来确定。与此同时,粒子的飞行速度直接关系到每个粒子的飞行距离以及方向。粒子群优化算法最大的优势就在于它不需要依靠大量的经验参数,简捷实用、适用于并行处理、具备较快的收敛速度等[3],而它的弊端则是收敛精度不够高、容易局限于局部的极值。

  神经网络算法在生物信息学中的主要作用是用来对生物神经系统信息处理过程的模拟。神经网络算法主要可以分为两个层面,一个为输出层面,另一个为输入层面。在这两个层面中间还存在些许隐藏的学习层面,这些学习层面中又包含了很多的结点[4].不同结点之间的连接方式多种多样,与此同时,每个结点如何把输入信号转换为输出信号的选择性也有很多[5].要想对神经网络进行有效的训练,就必须提供大量的数据信息。神经网络在得到训练后,就能够起到从相同类型没有处理过的数据中获取信息的作用。神经网络算法最大的不足在于,无法从大量的生物信息数据参数中提取出最简单的知识。

  3 参数化算法

  参数化算法作为一种先进的计算机算法,通过将计算实践和计算理论有效地结合在一起,从而不断提高解决生物信息学组合问题的效率。通过学习参数计算理论可以知道,在生物信息学中的某些NP-难问题能够实行参数化,简单来说就是合理设计出算法复杂度为“0”的计算方法。在这个过程中,c 作为一个常数,n 则作为问题的规模,k 是一个参数,这个参数的变化过程只能保持在一个小的范围中。一旦常数 c 的数值较小,参数化算法就能充分的抓住 k 作为一个小参数的特性,较为快速的破解掉生物信息学中的 NP-难问题。

  4 结束语

  综上所述,要想大力发展生物信息学,就必须将生物学和计算机学紧密的结合在一起。既要加强生物学方面知识的学习,还要不断对计算机算法进行改革创新,提高计算机算法的运行速度以及精确度,共同促进生物信息学稳定持续的发展。

  参考文献
  
  [1](沙特) Alsuw aiyel M H.算法设计技巧与分析[M].吴伟昶,方世昌,等,译。北京:电子工业出版社,2008:371-407.
  [2](美) Baxevanis And reas D,F rancis Ouellette B F.生物信息学:基因和蛋白质分析的实用指南[M].李衍达,孙之荣,等,译。北京:清华大学出版社,2008:13-120.
  [3]杨久俊,邓辉文,滕姿。基于混沌免疫进化算法的聚类算法分析[J].计算机科学,2008,8:154-156.
  [4]谢民主。单体型组装问题参数化建模及算法研究[D].长沙:中南大学,2008.
  [5]黄艳新,周春光,邹淑雪,等。一种求解类覆盖问题的混合算法[J].软件学报,2009,16(4):513-522.

相关内容推荐
相关标签:生物信息学论文
返回:生物工程论文