arXiv preprint ·
Pangenome Optimization via Elastic Degenerate Strings
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets. A pangenome, consisting of variations observed in a population along the genome sequences, can be naturally encoded as an EDS. Pattern matching and comparison problems on pangenome representations such as EDSes have been widely studied in the literature, but optimizing the pangenome properties during its construction has been largely omitted. We fill this gap by showing how methods originally developed for the related problem of founder reconstruction can be adapted to minimize, in linear time, the total cardinality of the EDS sets or the total size of the EDS strings, given suitable multiple alignments representing the input data. We provide an implementation for the minimum-cardinality criterion in a tool mincard, and conduct the first experiments on scalable pangenome optimization via EDSes. The code and experiments are available at https://github.com/algbio/eds.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation
Improved Algorithms for the Remote Point Problem
$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
Exponential Quantum Advantage in Testing Fourier Dimensionality
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.