.png){kind=icon}
.png){kind=icon}
Return
Large-Scale Multiple Sequence Alignment and the Maximum Weight Trace Alignment Merging Problem
.png){kind=icon}
OA
AI
DOI：10.1109/TCBB.2022.3191848.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Merging
Estimation
Corporate acquisitions
Optimization
Clustering algorithms
Pipelines
Markov processes
Multiple sequence alignment
maximum weight trace
Markov clustering
Journal
I
IF:
3.4
Papers:
3.3K
Citations:
6.4K
