Search

Indexing very large collections of strings, such as those produced by the widespread next generation sequencing technologies, heavily relies on multi-string generalization of the Burrows–Wheeler Transform (BWT): large requirements of in-memory approaches have stimulated recent developments on external memory algorithms. The related problem of computing the Longest Common Prefix (LCP) array of a set of strings is instrumental to compute the suffix-prefix overlaps among strings, which is an essential step for many genome assembly algorithms. In a previous paper, we presented an in-memory divide-and-conquer method for building the BWT and LCP where we merge partial BWTs with a forward approach to sort suffixes. In this paper, we propose an alternative backward strategy to develop an external memory method to simultaneously build the BWT and the LCP array on a collection of m strings of different lengths. The algorithm over a set of strings having constant length k has O ( m k l ) time and I/O volume, using O ( k + m ) main memory, where l is the maximum value in the LCP array.

Computational pangenomics is an emerging research field that is changing the way computer scientists are facing challenges in biological sequence analysis. In past decades, contributions from combinatorics, stringology, graph theory and data structures were essential in the development of a plethora of software tools for the analysis of the human genome. These tools allowed computational biologists to approach ambitious projects at population scale, such as the 1000 Genomes Project. A major contribution of the 1000 Genomes Project is the characterization of a broad spectrum of genetic variations in the human genome, including the discovery of novel variations in the South Asian, African and European populations—thus enhancing the catalogue of variability within the reference genome. Currently, the need to take into account the high variability in population genomes as well as the specificity of an individual genome in a personalized approach to medicine is rapidly pushing the abandonment of the traditional paradigm of using a single reference genome. A graph-based representation of multiple genomes, or a graph pangenome, is replacing the linear reference genome. This means completely rethinking well-established procedures to analyze, store, and access information from genome representations. Properly addressing these challenges is crucial to face the computational tasks of ambitious healthcare projects aiming to characterize human diversity by sequencing 1M individuals (Stark et al. 2019). This tutorial aims to introduce readers to the most recent advances in the theory of data structures for the representation of graph pangenomes. We discuss efficient representations of haplotypes and the variability of genotypes in graph pangenomes, and highlight applications in solving computational problems in human and microbial (viral) pangenomes.

Indexing very large collections of strings, such as those produced by the widespread next generation sequencing technologies, heavily relies on multistring generalization of the Burrows-Wheeler Transform (BWT): large requirements of in-memory approaches have stimulated recent developments on external memory algorithms. The related problem of computing the Longest Common Prefix (LCP) array of a set of strings is instrumental to compute the suffix-prefix overlaps among strings, which is an essential step for many genome assembly algorithms. In a previous paper, we presented an in-memory divide-and-conquer method for building the BWT and LCP where we merge partial BWTs with a forward approach to sort suffixes. In this paper, we propose an alternative backward strategy to develop an external memory method to simultaneously build the BWT and the LCP array on a collection of m strings of different lengths. The algorithm over a set of strings having constant length k has O(mkl) time and I/O volume, using O(k + m) main memory, where l is the maximum value in the LCP array., Theoretical Computer Science (2020). arXiv admin note: text overlap with arXiv:1607.08342

International audience; Haplotype assembly is the computational problem of reconstructing the two parental copies, called haplotypes, of each chromosome starting from sequencing reads, called fragments, possibly affected by sequencing errors. Minimum Error Correction (MEC) is a prominent computational problem for haplotype assembly and, given a set of fragments , aims at reconstructing the two haplotypes by applying the minimum number of base corrections. By using novel combinatorial properties of MEC instances, we are able to provide new results on the fixed-parameter tractability and approx-imability of MEC. In particular, we show that MEC is in FPT when para-meterized by the number of corrections, and, on " gapless " instances, it is in FPT also when parameterized by the length of the fragments, whereas the result known in literature forces the reconstruction of complementary haplotypes. Then, we show that MEC cannot be approximated within any constant factor while it is approximable within factor O(log nm) where nm is the size of the input. Finally, we provide a practical 2-approximation algorithm for the Binary MEC, a variant of MEC that has been applied in the framework of clustering binary data.

The Minimum-Recombinant Haplotype Configuration problem (MRHC) has been highly successful in providing a sound combinatorial formulation for the important problem of genotype phasing on pedigrees. Despite several algorithmic advances and refinements that led to some efficient algorithms, its applicability to real datasets has been limited by the absence of some important characteristics of these data in its formulation, such as mutations, genotyping errors, and missing data. In this work, we propose the Haplotype Configuration with Recombinations and Errors problem (HCRE), which generalizes the original MRHC formulation by incorporating the two most common characteristics of real data: errors and missing genotypes (including untyped individuals). Although HCRE is computationally hard, we propose an exact algorithm for the problem based on a reduction to the well-known Satisfiability problem. Our reduction exploits recent progresses in the constraint programming literature and, combined with the use of state-of-the-art SAT solvers, provides a practical solution for the HCRE problem. Biological soundness of the phasing model and effectiveness (on both accuracy and performance) of the algorithm are experimentally demonstrated under several simulated scenarios and on a real dairy cattle population., 14 pages, 1 figure, 4 tables, the associated software reHCstar is available at http://www.algolab.eu/reHCstar

After the first draft of the human genome has been published, the study of genetic variations has attracted increasing attention as a medium to map observable characteristics (phenotypic traits) of individuals to their underlying genes and biological processes. Unfortunately, observing and obtaining directly the genetic data of interest is a long and expensive operation, especially for large populations. Less informative sources of data are instead available at a fraction of cost. Computational methods are then called to recover the original data of interest from their less informative observations. The design of efficient combinatorial algorithms to infer relevant data for genetic variation studies starting from less informative observations is the main aim of the work of this thesis. In particular, we focused on two different kinds of data of crucial importance for genetic variation studies: haplotypes and transcripts. In the first part of the thesis, we studied the Haplotype Inference (HI) problem that requires to infer, for each individual of a population, the genetic sequences inherited from each parent (haplotypes) starting from their conflation (genotype). We formulated and analyzed two different computational problems of haplotype inference: the pure parsimony xor-haplotyping problem (PPXH) and the minimum event haplotype configuration problem (MinEHC). In the first problem, the haplotype inference process is guided by the pure parsimony criterion and it starts from a recently proposed representation of genotypes, called xor-genotypes. For this problem, we presented exact and approximate solutions by providing (i) polynomial time exact algorithms for some restricted cases, (ii) a fixed-parameter algorithm for the general case, and (iii) a polynomial time k-approximation algorithm, where k is the maximum number of heterozygous individuals at a given marker locus. These results are based on some interesting combinatorial properties of a graph representation of the solutions. Furthermore, we proposed a heuristic algorithm that can scale to real-world large instances, as shown in an extensive experimental evaluation. In the second HI problem, we assumed that parental relationships among members of the population are known. In the thesis we formulated and studied the HI problem on such populations under the assumption that the two most frequent kinds of variation events, namely recombinations and mutations, can occur. This formulation significantly extends previous works where only one of them (or none) was allowed. We proved that the problem, called MinEHC, is computationally hard to solve or to approximate even on simple instances. However, we provided a heuristic algorithm that has shown extremely good performances, both in terms of accuracy and running times, on several simulated scenarios. The heuristic algorithm is based on a L-reduction from MinEHC to a well-known coding problem, Decoding of Linear Codes (DLC). By (heuristically) solving DLC, we are able to recover the set of genetic variations that have occurred in the population and, then, to infer the set of haplotypes. In the second part of the thesis, we analyzed the problem of predicting the gene structure by aligning transcript fragments to a reference genomic sequence. Traditional basic approaches focus on computing high-quality transcript alignments that should reveal the gene structure. However, inherent ambiguities in the transcript alignments could heavily affect the prediction quality. In the thesis, instead, we formulated the gene structure prediction problem as the problem of choosing the simplest gene structure that can “explain” ambiguous alignments of several transcript fragments. We proposed two fast algorithmic solutions for the two combinatorial problems that stem from such formulation. The first algorithm efficiently computes all the possible (and biologically meaningful) alignments of a given transcript against a reference genomic sequence. The second algorithm, given all the possible alignments of a set of transcripts, extracts a single factorization for each transcript such that the induced gene structure is composed by the minimum number of expressed regions (exons). We also conducted an experimental evaluation of our strategy on a significant set of genes, and promising preliminary results have emerged even in absence of specific biological criteria.

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the $k$-anonymity. This approach requires that the rows of a table are partitioned in clusters of size at least $k$ and that all the rows in a cluster become the same tuple, after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be APX-hard even when the records values are over a binary alphabet and $k=3$, and when the records have length at most 8 and $k=4$ . In this paper we study how the complexity of the problem is influenced by different parameters. In this paper we follow this direction of research, first showing that the problem is W[1]-hard when parameterized by the size of the solution (and the value $k$). Then we exhibit a fixed parameter algorithm, when the problem is parameterized by the size of the alphabet and the number of columns. Finally, we investigate the computational (and approximation) complexity of the $k$-anonymity problem, when restricting the instance to records having length bounded by 3 and $k=3$. We show that such a restriction is APX-hard., Comment: 22 pages, 2 figures

Feature embedding methods have been proposed in the literature to represent sequences as numeric vectors to be used in some bioinformatics investigations, such as family classification and protein structure prediction. Recent theoretical results showed that the well-known Lyndon factorization preserves common factors in overlapping strings [1]. Surprisingly, the fingerprint of a sequencing read, which is the sequence of lengths of consecutive factors in variants of the Lyndon factorization of the read, is effective in capturing sequence similarities, suggesting it as basis for the definition of novel representations of sequencing reads. We propose a novel feature embedding method for Next-Generation Sequencing (NGS) data using the notion of fingerprint. We provide a theoretical and experimental framework to estimate the behaviour of fingerprints and of the k-mers extracted from it, called k-fingers, as possible feature embeddings for sequencing reads. As a case study to assess the effectiveness of such embeddings, we use fingerprints to represent RNA-Seq reads in order to assign them to the most likely gene from which they originated as fragments of transcripts of the gene. We provide an implementation of the proposed method in the tool lyn2vec, which produces Lyndon-based feature embeddings of sequencing reads.

Background SNP (single nucleotide polymorphisms) genotype data are increasingly available in cattle populations and, among other things, can be used to predict carriers of specific mutations. It is therefore convenient to have a practical statistical method for the accurate classification of individuals into carriers and non-carriers. In this paper, we compared – through cross-validation– five classification models (Lasso-penalized logistic regression –Lasso, Support Vector Machines with either linear or radial kernel –SVML and SVMR, k-nearest neighbors –KNN, and multi-allelic gene prediction –MAG), for the identification of carriers of the TUBD1 recessive mutation on BTA19 (Bos taurus autosome 19), known to be associated with high calf mortality. A population of 3116 Fleckvieh and 392 Brown Swiss animals genotyped with the 54K SNP-chip was available for the analysis. Results In general, the use of SNP genotypes proved to be very effective for the identification of mutation carriers. The best predictive models were Lasso, SVML and MAG, with an average error rate, respectively, of 0.2 %, 0.4 % and 0.6 % in Fleckvieh, and 1.2 %, 0.9 % and 1.7 % in Brown Swiss. For the three models, the false positive rate was, respectively, 0.1 %, 0.1 % and 0.2 % in Fleckvieh, and 3.0 %, 2.4 % and 1.6 % in Brown Swiss; the false negative rate was 4.4 %, 7.6 %1.0 % in Fleckvieh, and 0.0 %, 0.1% and 0.8 % in Brown Swiss. MAG appeared to be more robust to sample size reduction: with 25 % of the data, the average error rate was 0.7 % and 2.2 % in Fleckvieh and Brown Swiss, compared to 2.1 % and 5.5 % with Lasso, and 2.6 % and 12.0 % with SVML. Conclusions The use of SNP genotypes is a very effective and efficient technique for the identification of mutation carriers in cattle populations. Very few misclassifications were observed, overall and both in the carriers and non-carriers classes. This indicates that this is a very reliable approach for potential applications in cattle breeding., BMC Genomics, 17