Question

多序列比对的分类

Answer 1

目前,构建多序列比对模型的方法大体可以分为以下三类：
手工比对方法
手工比对方法在文献中经常看到。因为难免加入一些主观因素，手工比对通常被认为有很大的随意性。其实，即使用计算机程序进行自动比对，所得结果中的片面性也不能予以忽视。在运行经过测试并具有比较高的可信度的计算机程序基础上，结合实验结果或文献资料，对多序列比对结果进行手工修饰，应该说是非常必要的。
渐进法
渐进比对思想对于多个序列两两比对并且根据不同策略构建距离矩阵，反映序列之间的远近关系，然后根据距离矩阵计算产生系统进化指导树，对关系密切的序列进行加权，然后从最紧密的两条序列开始，逐步引入临近的序列，并不断重新构建比对，直到所有序列都被加入为止。根据不同距离策略，主要算法有：Feng-Doolittle算法及以其为基础的改进程序包CLUSTER W,Multal，Pileup。
同步法
同步法即同时比对所有序列。首先，确定某个目标函数，使得目标函数反映出每个多序列比对的质量。目标函数值越高，比对性能越好。对于序列数目多的情况下，在所有可能的多序列比对中，找出使得目标函数值最佳的比对，是一个NP-Complete问题。目前，由同时比对10条序列的MSA程序包，还有应用于多序列比对问题的随机启发式算法，模拟退火 算法，图像取样，遗传算法 等。