Pangenome comparison via ED strings.
| Autor: | Gabory E; Centrum Wiskunde & Informatica, Amsterdam, Netherlands., Mwaniki MN; Department of Computer Science, University of Pisa, Pisa, Italy., Pisanti N; Department of Computer Science, University of Pisa, Pisa, Italy., Pissis SP; Centrum Wiskunde & Informatica, Amsterdam, Netherlands.; Department of Computer Science, Vrije Universiteit, Amsterdam, Netherlands., Radoszewski J; Institute of Informatics, University of Warsaw, Warsaw, Poland., Sweering M; Centrum Wiskunde & Informatica, Amsterdam, Netherlands., Zuba W; Centrum Wiskunde & Informatica, Amsterdam, Netherlands. |
|---|---|
| Jazyk: | angličtina |
| Zdroj: | Frontiers in bioinformatics [Front Bioinform] 2024 Sep 26; Vol. 4, pp. 1397036. Date of Electronic Publication: 2024 Sep 26 (Print Publication: 2024). |
| DOI: | 10.3389/fbinf.2024.1397036 |
| Abstrakt: | Introduction: 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. Methods: In this study, we define notions of matching statistics 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 intersection graph of two ED strings. Results: We also implemented our methods as a software tool for pangenome comparison and evaluated their efficiency and effectiveness using both synthetic and real datasets. Discussion: 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. Competing Interests: The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest. (Copyright © 2024 Gabory, Mwaniki, Pisanti, Pissis, Radoszewski, Sweering and Zuba.) |
| Databáze: | MEDLINE |
| Externí odkaz: |
|