Data from: A simulation-based approach to statistical alignment

Classic alignment algorithms utilize scoring functions which maximize similarity or minimize edit distances. These scoring functions account for both insertion-deletion (indel) and substitution events. In contrast, alignments based on stochastic models aim to explicitly describe the evolutionary dynamics of sequences by inferring relevant probabilistic parameters from input sequences. Despite advances in stochastic modeling during the last two decades, scoring-based methods are still dominant, partially due to slow running times of probabilistic approaches. Alignment inference using stochastic models involves estimating the probability of events, such as the insertion or deletion of a specific number of characters. In this work, we present SimBa-SAl, a simulation-based approach to statistical alignment inference, which relies on an explicit continuous Markov process for both indels and substitutions. SimBa-SAl has several advantages. First, using simulations, it decouples the estimation of event probabilities from the inference stage, which allows the introduction of accelerations to the alignment inference procedure. Second, it is general and can accommodate various stochastic models of indel formation. Finally, it allows computing the maximum-likelihood alignment, the probability of a given pair of sequences integrated over all possible alignments, and sampling alternative alignments according to their probability. We first show that SimBa-SAl allows accurate estimation of parameters of the long-indel model previously developed by Miklós, Lunter and Holmes in 2004. We next show that SimBa-SAl is more accurate than previously developed pairwise alignment algorithms, when analyzing simulated as well as empirical datasets. Finally, we study the goodness-of-fit of the long-indel and TKF91 models. We show that while the long-indel model fits the datasets better than TKF91, there is still room for improvement concerning the realistic modeling of evolutionary sequence dynamics.经典序列比对算法通常采用打分函数，以最大化序列相似性或最小化编辑距离为目标。此类打分函数同时考虑插入-缺失（insertion-deletion, indel）与替换事件。 与之相对，基于随机模型的比对方法旨在通过从输入序列中推断相关概率参数，显式刻画序列的演化动力学过程。尽管近二十年来随机建模技术已有长足进展，但基于打分的方法仍占据主导地位，部分原因在于概率类方法的运行速度较慢。 基于随机模型的比对推断需要估算各类事件的发生概率，例如特定数目字符的插入或缺失事件。 本研究提出了SimBa-SAl，一种基于模拟的统计比对推断方法，其针对插入缺失与替换事件采用显式连续马尔可夫过程建模。 SimBa-SAl具备多项优势：其一，通过模拟手段将事件概率估算与推断阶段解耦，从而可引入加速策略优化比对推断流程；其二，该方法具备通用性，可适配多种插入缺失形成的随机模型；其三，其支持计算最大似然比对、在所有可能比对空间上积分得到的给定序列对的概率，以及依据概率采样备选比对结果。 本研究首先验证了SimBa-SAl可精准估算Miklós、Lunter与Holmes于2004年提出的长插入缺失（long-indel）模型的参数。 随后的实验表明，在分析模拟数据集与真实数据集时，SimBa-SAl的比对精度优于此前已有的双序列比对算法。 最后，本研究还对长插入缺失模型与TKF91模型的拟合优度展开了分析，结果显示，尽管长插入缺失模型的拟合效果优于TKF91模型，但在演化序列动力学的写实建模方面仍有改进空间。