In recent times there has been an increase in the amount of individual genomes sequenced for species, which are highly repetitive sequence collections known as pangenomes. Pangenomes can be represented in different ways, from strings to graphs, each with its own advantages and disadvantages. We focus on one of these representations: elastic-degenerate strings. An elastic-degenerate string (EDS) is a string whose symbols, called degenerate symbols , are comprised of one or more strings of any length, including the empty string (hence, we can have several alternatives per symbol). In this paper, we generalize to EDS the Burrows-Wheeler transform extended to a string collection. We define the Burrows-Wheeler transform of an Elastic-Degenerate String (called EDS-BWT), and show that it is a reversible transformation and it can be used for pattern matching, i.e., for finding the occurrences of a standard string pattern within an EDS. In particular, the inner properties of the classical Burrows-Wheeler transform are adapted in order to design a backward search strategy for pattern matching on an EDS. Furthermore, we analyze the worst-case complexity of that backward search. Thanks to our prototype edsBWTSearch , we experimentally compare our pattern matching approach to other existing tools managing elastic degenerate strings.

Applications in domains ranging from bioinformatics to advertising feature strings (sequences of letters over some alphabet) that come with numerical scores (utilities). The utilities quantify the importance, interest, profit, or risk of the letters occurring at every position of a string. For instance, DNA fragments generated by sequencing machines come with a confidence score per position. Motivated by the ever-increasing rate of generating such data, as well as by their importance in several domains, we introduce Useful String Indexing (USI), a natural generalization of the classic String Indexing problem. Given a string$S$(the text) of length$n$, USI asks for preprocessing$S$into a compact data structure supporting the following queries efficiently: given a shorter string$P$(the pattern), return the global utility$U(P)$of$P$in$S$, where$U$is a function that maps any string$P$to a utility score based on the utilities of the letters of every occurrence of$P$in$S$. Our work also makes the following contributions: (1) We propose a novel and efficient data structure for USI based on finding the top-$K$frequent substrings of$S$. (2) We propose a linear-space data structure that can be used to mine the top-$K$frequent substrings of$S$or to tune the parameters of the USI data structure. (3) We propose a novel space-efficient algorithm for estimating the set of the top-$K$frequent substrings of$S$, thus improving the construction space of the data structure for USI. (4) We show that popular space-efficient top-$K$frequent item mining strategies employed by state-of-the-art algorithms do not smoothly translate from items to substrings. (5) Using billion-letter datasets, we experimentally demonstrate that: (i) our top-$K$frequent substring mining algorithms are accurate and scalable, unlike two state-of-the-art methods; and (ii) our USI data structures are up to 15 times faster in querying than 4 nontrivial baselines while occupying the same space with them.

Pangenomics is a rapidly evolving field in bioinformatics that enables the study of genetic diversity within populations by representing multiple genomes in a unified structure. Unlike traditional linear reference genomes, pangenomes provide a more comprehensive framework for analyzing genomic variations. Recent advancements in machine learning (ML) for DNA classification, based on large language models (LLMs) such as generative pre-trained transformers (GPT), have achieved state-of-the-art performance. However, these models often require extensive computational resources and do not leverage domain-specific bioinformatics techniques for pangenomic analysis. In this work, we introduce a novel Graph Machine Learning approach for DNA classification (GDNA) based on graph kernels. We represent DNA sequences using de Bruijn graphs, which allow a structured and information-rich representation of genomic data. We compute the similarity between graphs via the Weisfeiler-Lehman (WL) graph kernel and perform classification using a Support Vector Machine (SVM). Experimental evaluation on the Genomic Benchmarks dataset demonstrates that GDNA is competitive with state-of-the-art LLMs such as HyenaDNA, DNABERT, and GPT-based approaches on artificial and real-world DNA classification tasks, without the need for pre-training and with significantly higher efficiency. Overall, GDNA is an efficient and competitive DNA classifier that leverages pangenomes and graph-based representations, providing a valuable tool for genomic and pangenomic analysis in bioinformatics and precision medicine.

A string is often provided with numerical scores (utilities) which quantify the importance, interest, profit, or risk of the letters occurring at every position of the string. For example, every DNA fragment produced by modern sequencing machines comes with a confidence score per position. Motivated by the abundance of strings with utilities, we introduce Utility-oriented String Mining (USM), a natural generalization of the classic frequent substring mining problem. Given a string S of length n and a threshold 𝒱, USM asks for every string R whose utility U (R) is at least 𝒱, where U is a function that maps R to a utility score based on the utilities of all letters of every occurrence of R in S. In addition, our work makes the following contributions: (1) We identify a class 𝕌 of utility functions for which USM admits an 𝒪 (n2)-time algorithm. (2) We prove that no listing algorithm solves the USM problem in subquadratic time for every utility function, or even for every function in 𝕌. (3) We propose an 𝒪 (n log n)-time algorithm that solves USM for a class of monotone functions from 𝕌. (4) We design another 𝒪 (n log n)-time algorithm for the same problem that is comparable in runtime but offers drastic space savings in practice when, in addition, a lower bound on the length of the output strings is provided as input. (5) We demonstrate experimentally using publicly available, billion-letter datasets that our algorithms are many times more efficient, in terms of runtime and/or space, compared to an Apriori-like baseline which employs advanced string processing tools.

It is known that the exact form of the Burrows-Wheeler Transform (BWT) of a string collection depends, in most implementations, on the input order of the strings in the collection. Reordering strings of an input collection affects the number of equal-letter runs r, arguably the most important parameter of BWT-based data structures, such as the FM-index or the r-index. Bentley, Gibney, and Thankachan [ESA 2020] introduced a linear-time algorithm for computing the permutation of the input collection which yields the minimum number of runs of the resulting BWT. In this paper, we present the first tool that guarantees a Burrows-Wheeler Transform with minimum number of runs (optBWT), by combining i) an algorithm that builds the BWT from a string collection (either SAIS-based [Boucher et al., SPIRE 2021] or BCR [Bauer et al., CPM 2011]); ii) the SAP array data structure introduced in [Cox et al., Bioinformatics, 2012]; and iii) the algorithm by Bentley et al. We present results both on real-life and simulated data, showing that the improvement achieved in terms of r with respect to the input order is significant and the overhead created by the computation of the optimal BWT negligible, making our tool competitive with other tools for BWT-computation in terms of running time and space usage. In particular, on real data the optBWT obtains up to 31 times fewer runs with only a 1.39$\times$ slowdown. Source code is available at https://github.com/davidecenzato/optimalBWT.git.

Molecular phylogenetics is a fundamental branch of biology. It studies the evolutionary relationships among the individuals of a population through their biological sequences, and may provide insights about the origin and the evolution of viral diseases, or highlight complex evolutionary trajectories. In this paper we develop a method called phyBWT, describing how to use the extended Burrows-Wheeler Transform (eBWT) for a collection of DNA sequences to directly reconstruct phylogeny, bypassing the alignment against a reference genome or de novo assembly. Our phyBWT hinges on the combinatorial properties of the eBWT positional clustering framework. We employ eBWT to detect relevant blocks of the longest shared substrings of varying length (unlike the k-mer-based approaches that need to fix the length k a priori), and build a suitable decomposition leading to a phylogenetic tree, step by step. As a result, phyBWT is a new alignment-, assembly-, and reference-free method that builds a partition tree without relying on the pairwise comparison of sequences, thus avoiding to use a distance matrix to infer phylogeny. The preliminary experimental results on sequencing data show that our method can handle datasets of different types (short reads, contigs, or entire genomes), producing trees of quality comparable to that found in the benchmark phylogeny.

BACKGROUND: The development of Next Generation Sequencing (NGS) has had a major impact on the study of genetic sequences. Among problems that researchers in the field have to face, one of the most challenging is the taxonomic classification of metagenomic reads, i.e., identifying the microorganisms that are present in a sample collected directly from the environment. The analysis of environmental samples (metagenomes) are particularly important to figure out the microbial composition of different ecosystems and it is used in a wide variety of fields: for instance, metagenomic studies in agriculture can help understanding the interactions between plants and microbes, or in ecology, they can provide valuable insights into the functions of environmental communities. RESULTS: In this paper, we describe a new lightweight alignment-free and assembly-free framework for metagenomic classification that compares each unknown sequence in the sample to a collection of known genomes. We take advantage of the combinatorial properties of an extension of the Burrows-Wheeler transform, and we sequentially scan the required data structures, so that we can analyze unknown sequences of large collections using little internal memory. The tool LiME (Lightweight Metagenomics via eBWT) is available at https://github.com/veronicaguerrini/LiME . CONCLUSIONS: In order to assess the reliability of our approach, we run several experiments on NGS data from two simulated metagenomes among those provided in benchmarking analysis and on a real metagenome from the Human Microbiome Project. The experiment results on the simulated data show that LiME is competitive with the widely used taxonomic classifiers. It achieves high levels of precision and specificity - e.g. 99.9% of the positive control reads are correctly assigned and the percentage of classified reads of the negative control is less than 0.01% - while keeping a high sensitivity. On the real metagenome, we show that LiME is able to deliver classification results comparable to that of MagicBlast. Overall, the experiments confirm the effectiveness of our method and its high accuracy even in negative control samples.

In this paper we study the family of permutations avoiding the pattern 122+3 (trivially equivalent to those avoiding 123⎵4), which extend the popular 123-avoiding permutations. In particular we provide an algorithmic description of a generating tree for these permutations, that is a way to build ev ery object of a given size n + 1 in a unique way by performing local modifications on an object of size n. Our algorithm leads to a direct bijection between 123⎵4-avoiding permutations and valley-marked Dyck paths. It extends a known bijection between 123-avoiding permutations and Dyck paths, and makes explicit the connection between these objects that was earlier obtained by Callan through a series of non-trivial bijective steps. In particular our construction is simple enough to allow for efficient exhaustive generation.

In this paper, we enumerate two families of pattern-avoiding permutations: those avoiding the vincular pattern $2\underbracket{41}3$, which we call semi-Baxter permutations, and those avoiding the vincular patterns $2\underbracket{41}3$, $3\underbracket{14}2,$ and $3\underbracket{41}2$, which we call strong-Baxter permutations. We call semi-Baxter numbers and strong-Baxter numbers the associated enumeration sequences. We prove that the semi-Baxter numbers enumerate in addition plane permutations (avoiding $2\underbracket{14}3$). The problem of counting these permutations was open and has given rise to several conjectures, which we also prove in this paper. For each family (that of semi-Baxter---or, equivalently, plane---and that of strong-Baxter permutations), we describe a generating tree, which translates into a functional equation for the generating function. For semi-Baxter permutations, it is solved using (a variant of) the kernel method: this gives an expression for the generating function while also proving its D-finiteness. From the obtained generating function, we derive closed formulas for the semi-Baxter numbers, a recurrence that they satisfy, as well as their asymptotic behavior. For strong-Baxter permutations, we show that their generating function is (a slight modification of) that of a family of walks in the quarter plane, which is known to be non--D-finite.