Biology subjects

Tomescu, A. I.

Publications and source records attributed to Tomescu, A. I..

6 recordsLinked to original sources

bioRxiv2023

Accurate Flow Decomposition via Robust Integer Linear Programming

Minimum flow decomposition (MFD) is a common problem across various fields of Computer Science, where a flow is decomposed into a minimum set of weighted paths. However, in Bioinformatics applications, such as RNA transcript or quasi-species assembly, the flow is erroneous, since is obtained from noisy read coverages. Typical generalizations of the MFD problem to handle errors are based on least-squares formulations, or on modeling the erroneous flow values as ranges. All of these are thus focused on error-handling at the level of individual edges. Interpreting the flow decomposition problem as a robust optimization problem, we lift error-handling from individual edges to solution paths. As such, we introduce a new minimum path-error flow decomposition problem, for which we give an efficient Integer Linear Programming formulation. Our experimental results reveal that our formulation can account for errors with an accuracy significantly surpassing that of previous error-handling formulations, with computational requirements that remain practical.

bioinformatics↗

bioRxiv2023

The omnitig framework can improve genome assembly contiguity in practice

Despite the long history of genome assembly research, there remains a large gap between the theoretical and practical work. There is practical software with little theoretical underpinning of accuracy on one hand and theoretical algorithms which have not been adopted in practice on the other. In this paper we attempt to bridge the gap between theory and practice by showing how the theoretical safe-and-complete framework can be integrated into existing assemblers in order to improve contiguity. The optimal algorithm in this framework, called the omnitig algorithm, has not been used in practice due to its complexity and its lack of robustness to real data. Instead, we pursue a simplified notion of omnitigs, giving an efficient algorithm to compute them and demonstrating their safety under certain conditions. We modify two assemblers (wtdbg2 and Flye) by replacing their unitig algorithm with the simple omnitig algorithm. We test our modifications using real HiFi data from the Drosophilia melanogaster and the Caenorhabditis elegans genome. Our modified algorithms lead to a substantial improvement in alignment-based contiguity, with negligible computational costs and either no or a small increase in the number of misassemblies.

bioinformatics↗

bioRxiv2023

Sensitive inference of alignment-safe intervalsfrom biodiverse protein sequence clusters usingEMERALD

Sequence alignments are the foundation of life science research, but most innovation focused on optimal alignments, while ignoring information derived from suboptimal solutions. We argue that one optimal alignment per pairwise sequence comparison was a reasonable approximation when dealing with very similar sequences, but is insufficient when exploring the biodiversity of the protein universe at tree-of-life scale. To overcome this limitation, we introduce pairwise alignment-safety to uncover the amino acid positions robustly shared across all suboptimal solutions. We implemented this approach into EMERALD, a dedicated software solution for alignment-safety inference and apply it to 400k sequences from the SwissProt database.

bioinformatics↗

bioRxiv2022

Extremely-fast construction and querying of compacted and colored de Bruijn graphs with GGCAT

Compacted de Bruijn graphs are one of the most fundamental data structures in computational genomics. Colored compacted graphs Bruijn graphs are a variant built on a collection of sequences, and associate to each k-mer the sequences in which it appears. We present GGCAT, a tool for constructing both types of graphs, based on a new approach merging the k-mer counting step with the unitig construction step, and on numerous practical optimizations. For compacted de Bruijn graph construction, GGCAT achieves speed-ups of 3-21x compared to the state-of-the-art tool Cuttlefish 2 (Khan and Patro, Genome Biology, 2022). When constructing the colored variant, GGCAT achieves speed-ups of 5-39x compared to the state-of-the-art tool BiFrost (Holley and Melsted, Genome Biology, 2020). Additionally, GGCAT is up to 480x faster than BiFrost for batch sequence queries on colored graphs.

bioinformatics↗

bioRxiv2022

GraphChainer: Co-linear Chaining for Accurate Alignment of Long Reads to Variation Graphs

Aligning reads to a variation graph is a standard task in pangenomics, with downstream applications such as improving variant calling. While the vg toolkit (Garrison et al., Nature Biotechnology, 2018) is a popular aligner of short reads, GraphAligner (Rautiainen and Marschall, Genome Biology, 2020) is the state-of-the-art aligner of erroneous long reads. GraphAligner works by finding candidate read occurrences based on individually extending the best seeds of the read in the variation graph. However, a more principled approach recognized in the community is to co-linearly chain multiple seeds. We present a new algorithm to co-linearly chain a set of seeds in a string labeled acyclic graph, together with the first efficient implementation of such a co-linear chaining algorithm into a new aligner of erroneous long reads to acyclic variation graphs, GraphChainer. Compared to GraphAligner, GraphChainer aligns 12% to 17% more reads, and 21% to 28% more total read length, on real PacBio reads from human chromosomes 1, 22 and the whole human pangenome. On both simulated and real data, GraphChainer aligns between 95% and 99% of all reads, and of total read length. We also show that minigraph (Li et al., Genome Biology, 2020) and minichain (Chandra and Jain, RECOMB, 2023) obtain an accuracy of less than 60% on this setting. GraphChainer is freely available at https://github.com/algbio/GraphChainer. The datasets and evaluation pipeline can be reached from the previous address.

bioinformatics↗

bioRxiv2021

Matchtigs: minimum plain text representation of kmer sets

We propose a polynomial algorithm computing a minimum plain-text representation of kmer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model organisms or bacterial pangenomes, with only a minor runtime increase, we shrink the representation by up to 60% over unitigs and 27% over previous work. Additionally, the number of strings is decreased by up to 97% over unitigs and 91% over previous work. Finally, a small representation has advantages in downstream applications, as it speeds up SSHash-Lite queries by up to 4.26x over unitigs and 2.10x over previous work. Availabilitymatchtigs: https://github.com/algbio/matchtigs SSHash-Lite: https://github.com/jermp/sshash-lite

bioinformatics↗