Multiple alignment by aligning alignments
Multiple alignment by aligning alignments
复制标题
DOI：
10.1093/bioinformatics/btm226
复制
发表时间：
2007-07-01
期刊：
影响因子：
5.8
通讯作者：
Kececioglu, John D.
中科院分区：
文献类型：
--
作者：
Wheeler, Travis J.;Kececioglu, John D.
动机：多序列比对是生物信息学的一项基本任务。当前的工具通常通过合并子对齐来形成初始对齐，然后通过重复拆分和合并子对齐来优化该对齐，以获得改进的最终对齐。一般来说，这种形式-润色策略包含几个阶段，并且在每个阶段都尝试了大量方法。我们仔细研究了：(1)如何利用一种新的对齐算法来最优地解决合并子对齐的常见子问题；(2)每个阶段的最佳选择方法是什么，以获得最高质量的对齐。结果：我们研究了多重比对的形状-抛光策略的六个阶段：参数选择、距离估计、合并树构建、序列对加权、比对合并和抛光。对于每个阶段，我们考虑新的方法以及标准的方法。有趣的是，校准质量的最大收益来自(i)使用标准化校准成本的新方法估计距离，以及（ii）使用3-cuts的新方法抛光。对参数值oracle的实验表明，通过对对齐参数的输入依赖选择，可能会获得很大的质量增益，并且我们提出了一种有前途的方法来构建这样的oracle。将每个阶段的最佳方法结合起来，产生了一个新的工具，我们称之为Opal，它在基准校准上与顶级工具的质量相匹配，而不使用校准一致性或疏水间隙惩罚。
Motivation: Multiple sequence alignment is a fundamental task in bioinformatics. Current tools typically form an initial alignment by merging subalignments, and then polish this alignment by repeated splitting and merging of subalignments to obtain an improved final alignment. In general this form-and-polish strategy consists of several stages, and a profusion of methods have been tried at every stage. We carefully investigate: ( 1) how to utilize a new algorithm for aligning alignments that optimally solves the common subproblem of merging subalignments, and ( 2) what is the best choice of method for each stage to obtain the highest quality alignment.Results: We study six stages in the form-and-polish strategy for multiple alignment: parameter choice, distance estimation, merge-tree construction, sequence-pair weighting, alignment merging, and polishing. For each stage, we consider novel approaches as well as standard ones. Interestingly, the greatest gains in alignment quality come from (i) estimating distances by a new approach using normalized alignment costs, and (ii) polishing by a new approach using 3-cuts. Experiments with a parameter-value oracle suggest large gains in quality may be possible through an input-dependent choice of alignment parameters, and we present a promising approach for building such an oracle. Combining the best approaches to each stage yields a new tool we call Opal that on benchmark alignments matches the quality of the top tools, without employing alignment consistency or hydrophobic gap penalties.