Gabory Esteban, Mwaniki Moses Njagi, Pisanti Nadia, Pissis Solon P, Radoszewski Jakub, Sweering Michelle, Zuba Wiktor
Centrum Wiskunde & Informatica, Amsterdam, Netherlands.
Department of Computer Science, University of Pisa, Pisa, Italy.
Front Bioinform. 2024 Sep 26;4:1397036. doi: 10.3389/fbinf.2024.1397036. eCollection 2024.
An elastic-degenerate (ED) string is a sequence of sets of strings. It can also be seen as a directed acyclic graph whose edges are labeled by strings. The notion of ED strings was introduced as a simple alternative to variation and sequence graphs for representing a pangenome, that is, a collection of genomic sequences to be analyzed jointly or to be used as a reference.
In this study, we define notions of of two ED strings as similarity measures between pangenomes and, consequently infer a corresponding distance measure. We then show that both measures can be computed efficiently, in both theory and practice, by employing the of two ED strings.
We also implemented our methods as a software tool for pangenome comparison and evaluated their efficiency and effectiveness using both synthetic and real datasets.
As for efficiency, we compare the runtime of the intersection graph method against the classic product automaton construction showing that the intersection graph is faster by up to one order of magnitude. For showing effectiveness, we used real SARS-CoV-2 datasets and our matching statistics similarity measure to reproduce a well-established clade classification of SARS-CoV-2, thus demonstrating that the classification obtained by our method is in accordance with the existing one.
弹性退化（ED）字符串是字符串集的序列。它也可以被看作是一个有向无环图，其边由字符串标记。ED字符串的概念被引入作为一种简单的替代方法，用于表示泛基因组的变异和序列图，即一组要联合分析或用作参考的基因组序列。
在本研究中，我们定义了两个ED字符串的概念作为泛基因组之间的相似性度量，并由此推断出相应的距离度量。然后我们表明，在理论和实践中，通过采用两个ED字符串的[此处原文缺失相关内容]，这两种度量都可以有效地计算。
我们还将我们的方法实现为一个用于泛基因组比较的软件工具，并使用合成数据集和真实数据集评估了它们的效率和有效性。
至于效率，我们将交集图方法的运行时间与经典乘积自动机构造进行比较，结果表明交集图快了多达一个数量级。为了证明有效性，我们使用真实的SARS-CoV-2数据集和我们的匹配统计相似性度量来重现一个已确立的SARS-CoV-2进化枝分类，从而表明我们的方法获得的分类与现有分类一致。
