论文部分内容阅读
生物信息学以计算机、网络为工具,用数学等科学理论、方法和技术研究生物大分子,主要包括脱氧核糖核酸(DNA)和蛋白质(Protein)的序列、结构和功能。生物序列的比对,是生物信息学中最基本、最重要的操作,在序列分析、基因识别、蛋白质结构预测、生物进化树的构建等领域中有着广泛的应用。通过序列比对可以发现生物序列中的功能、结构以及进化信息。在本文中,我们提出了可重构光总线并行计算模型LARPBS模型上的一个快速可扩放的双序列比对并行算法,以及用蚁群算法求解多序列比对问题的三种不同方法,并给出了该方面工作的进一步研究思路。生物序列的信息量很大,对其进行比对操作需要花费大量的计算时间,所以,序列比对的并行计算已经成为研究的一个热点问题。我们利用可重构的光总线并行计算模型LARPBS,设计了一个快速可扩放的双序列比对并行算法,对于长度为m、n的两个序列,该算法使用p个处理机可以在O(mn/p)时间完成序列的比对计算,这里,p满足1≤p≤max{m, n}。该算法允许通过对p的选取来调节处理机的个数和时间复杂度,使得算法不仅在计算时间上达到最优,而且具有很好的可扩放性。由于生物序列较长,求解序列比对特别是多重序列比对的计算复杂度较高。可以证明,即使对于最简单的计分函数,寻找最优的多重序列比对也是一个NP-完全问题。在实际计算中不太可能用精确的算法求得多重序列的准确比对,而只能用启发式的算法在合理的时间内求得近似解。本文研究了对生物序列如何用启发式的算法,在综合考虑解的正确性以及计算速度两方面因素的前提下,求得质量较高的多序列比对。我们设计了多重序列比对的蚁群求解算法Ant-Align,利用人工蚂蚁逐个选择各个序列中的字符进行配对。在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中的字符的概率,通过信息素的更新与调节相结合的策略,以及参数的动态自适应调节方法,有效的解决了局部收敛的问题,加强了算法寻求全局最优解的能力。针对Ant-Align算法在比对较长序列时正确性下降的问题,我们设计了基于分