Large-Scale Multiple Sequence Alignment and the Maximum Weight Trace Alignment Merging Problem
Large-Scale Multiple Sequence Alignment and the Maximum Weight Trace Alignment Merging Problem
复制标题
DOI：
10.1109/tcbb.2022.3191848
复制
发表时间：
2023-05-01
影响因子：
4.5
通讯作者：
Warnow，Tandy
中科院分区：
文献类型：
--
作者：
Zaharias，Paul;Smirnov，Vladimir;Warnow，Tandy
MAGUS是一种最新的多序列比对方法，可在具有挑战性的大型数据集上提供出色的准确性。MAGUS采用分而治之的方法：它将序列划分为不相交的集合，计算不相交集合上的对齐，然后使用一种称为图聚类方法（GCM）的技术合并对齐。为了理解MAGUS如此精确的原因，我们证明了GCM是NP-hard MWT-AM问题（最大权重跟踪，适用于对齐合并问题）的良好启发式方法。我们的研究使用了生物和模拟数据，确定了MWT-AM分数与对准精度非常相关，并提出了对GCM的改进，这对MWT-AM来说是更好的启发式方法。该研究提出了基于改进的分治策略的大规模MSA估计的新方向，其中合并步骤基于优化MWT-AM。MAGUS及其增强版本可在https://github.com/vlasmirnov/MAGUS上获得。
MAGUS is a recent multiple sequence alignment method that provides excellent accuracy on large challenging datasets. MAGUS uses divide-and-conquer: it divides the sequences into disjoint sets, computes alignments on the disjoint sets, and then merges the alignments using a technique it calls the Graph Clustering Method (GCM). To understand why MAGUS is so accurate, we show that GCM is a good heuristic for the NP-hard MWT-AM problem (Maximum Weight Trace, adapted to the Alignment Merging problem). Our study, using both biological and simulated data, establishes that MWT-AM scores correlate very well with alignment accuracy and presents improvements to GCM that are even better heuristics for MWT-AM. This study suggests a new direction for large-scale MSA estimation based on improved divide-and-conquer strategies, with the merging step based on optimizing MWT-AM. MAGUS and its enhanced versions are available at https://github.com/vlasmirnov/MAGUS.