Pangenome optimization reduces complexity of genetic variation data
Pangenome Optimization via Elastic Degenerate Strings
Data Structures and Algorithms
Summary
Genetic data from many individuals contains many variations, making it tricky to store and search efficiently. The authors show how to organize these variations into a special format called an Elastic Degenerate String that minimizes redundancy. Their approach runs quickly and creates smaller, easier-to-use genetic data representations. They also provide a tool and experiments to demonstrate this optimization.
What this means in practice
- •For bioinformatics software developers: Create tools that represent population genome variations more compactly to speed up genomic searches and analyses.
- •For genomic data engineers: Build optimized storage formats from multiple sequence alignments that minimize total size and complexity of pangenome datasets.
Authors
Nicola Rizzo, Sebastian Visan-Draghicescu, Nadia Pisanti, Veli Mäkinen
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.