Search

The notion of Lyndon word and Lyndon factorization has shown to have unexpected applications in theory as well as in developing novel algorithms on words. A counterpart to these notions are those of inverse Lyndon word and inverse Lyndon factorization. Differently from the Lyndon words, the inverse Lyndon words may be bordered. The relationship between the two factorizations is related to the inverse lexicographic ordering, and has only been recently explored. More precisely, a main open question is how to get an inverse Lyndon factorization from a classical Lyndon factorization under the inverse lexicographic ordering, named CFLin. In this paper we reveal a strong connection between these two factorizations where the border plays a relevant role. More precisely, we show two main results. We say that a factorization has the border property if a nonempty border of a factor cannot be a prefix of the next factor. First we show that there exists a unique inverse Lyndon factorization having the border property. Then we show that this unique factorization with the border property is the so-called canonical inverse Lyndon factorization, named ICFL. By showing that ICFL is obtained by compacting factors of the Lyndon factorization over the inverse lexicographic ordering, we provide a linear time algorithm for computing ICFL from CFLin.

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.

Chimeric RNAs are transcripts generated by gene fusion and intergenic splicing events, thus comprising nucleotide sequences from different genes. Recent studies have shown that some chimeric RNAs can play a role in cancer development, and so can be used as diagnostics biomarkers when specifically expressed in cancerous cells and tissues. Most gene fusion prediction tools rely on an initial alignment step. However, alignments might be biased, especially for chimeric reads, creating many false positives. Therefore, developing alignment-free prediction methods of fusion genes would be helpful and may provide new insights into the genomic breakage phenomenon in the cell. In this direction, machine learning could pave the way for new solutions, due to their success in predicting genomic regulatory elements and alternative junction events from the genomic context. To date, however, these techniques have had a marginal supporting role, and, furthermore, manually-curated data sets, that are crucial for model training, are often expensive, unreliable or simply unavailable. Here we propose a novel ML-based method that learn to recognize the hidden patterns that allow to identify chimeric RNAs deriving from oncogenic gene fusions. Preliminary comparison with another state-ofthe- art method shows promising results.

The Lyndon factorization of a word has been largely studied and recently variants of it have been introduced and investigated with different motivations. In particular, the canonical inverse Lyndon factorization ICFL(w) of a word w, introduced in [1], maintains the main properties of the Lyndon factorization since it can be computed in linear time and it is uniquely determined. In this paper we investigate new properties of this factorization with the aim of exploring their use in some classical queries on w. The main property we prove is related to a classical query on words. We prove that there are relations between the length of the longest common prefix (or longest common extension) lcp(x,y) of two different suffixes x,y of a word w and the maximum length M of two consecutive factors of ICFL(w). More precisely, M is an upper bound on the length of lcp(x,y). A main tool used in the proof of the above result is a property that we state for factors mi with nonempty borders in ICFL(w): a nonempty border of mi cannot be a prefix of the next factor mi+1. Another interesting result relates sorting of global suffixes, i.e., suffixes of a word w, and sorting of local suffixes, i.e., suffixes of products of factors in ICFL(w). This is the counterpart for ICFL(w) of the compatibility property, proved in [2,3] for the Lyndon factorization. Roughly, the compatibility property allows us to extend the mutual order between suffixes of products of the (inverse) Lyndon factors to the suffixes of the whole word. The last property we prove focuses on the Lyndon factorizations of a word and its factors. It suggests that the Lyndon factorizations of two words sharing a common overlap could be used to capture the common overlap of these two words.

The Lyndon factorization of a word has been extensively studied in different contexts and several variants of it have been proposed. In particular, the canonical inverse Lyndon factorization ICFL, introduced in [5], maintains the main properties of the Lyndon factorization since it can be computed in linear time and it is uniquely determined. In this paper we investigate new properties of this factorization with the purpose of exploring its use in string queries. As a main result, we prove an upper bound on the length of the longest common extension (or longest common prefix) for two factors of a word w. This bound is at most the maximum length of two consecutive factors of ICFL(w). A tool used in the proof is a property that we state for factors with nonempty borders in ICFL(w): a nonempty border of a factor mi cannot be a prefix of the next factor mi+1. Another interesting result relates sorting of global suffixes, i.e., suffixes of a word w, and sorting of local suffixes, i.e., suffixes of the factors in ICFL(w). Finally, given a word w and a factor x of w, we prove that their Lyndon factorizations share factors, except for the first and last term of the Lyndon factorization of x. This property suggests that, given two words sharing a common overlap, their Lyndon factorizations could be used to capture the common overlap of these two words.

Graph pangenomics is a new emerging field in computational biology that is changing the traditional view of a reference genome from a linear sequence to a new paradigm: a sequence graph (pangenome graph or simply pangenome) that represents the main similarities and differences in multiple evolutionary related genomes. The speed in producing large amounts of genome data, driven by advances in sequencing technologies, is far from the slow progress in developing new methods for constructing and analyzing a pangenome. Most recent advances in the field are still based on notions rooted in established and quite old literature on combinatorics on words, formal languages and space efficient data structures. In this paper we discuss two novel notions that may help in managing and analyzing multiple genomes by addressing a relevant question: how can we summarize sequence similarities and dissimilarities in large sequence data? The first notion is related to variants of the Lyndon factorization and allows to represent sequence similarities for a sample of reads, while the second one is that of sample specific string as a tool to detect differences in a sample of reads. New perspectives opened by these two notions are discussed.

Circular splicing systems are a mathematical model, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. A circular splicing language is a language generated by a circular splicing system. An open problem is to characterize regular circular splicing languages and the corresponding circular splicing systems. In this framework an important role is played by unavoidable sets. These sets have been considered in several contexts. In particular, Ehrenfeucht, Haussler and Rozenberg (1983) proved the following generalization of a famous Higman's theorem: the quasi-order induced by insertions of words from a fixed finite set is a well-quasi-order if and only if the finite set is unavoidable. In this paper we survey the known relations between unavoidable sets and regular circular languages. Motivated by these connections we give an alternative and simpler proof of the Ehrenfeucht, Haussler and Rozenberg result. Our proof is strongly based on a known characterization of unavoidable sets in terms of graphs associated with them.

Representations of biological sequences facilitating sequence comparison are crucial in several bioinformatics tasks. Recently, the Lyndon factorization has been proved to preserve common factors in overlapping reads, thus leading to the idea of using factorizations of sequences to define measures of similarity between reads. In this paper we propose as a signature of sequencing reads the notion of fingerprint, i.e., the sequence of lengths of consecutive factors in Lyndon-based factorizations of the reads. Surprisingly, fingerprints of reads are effective in preserving sequence similarities while providing a compact representation of the read, and so, k-mers extracted from a fingerprint, called k-fingers, can be used to capture sequence similarity between reads. We first provide a probabilistic framework to estimate the behaviour of fingerprints. Then we experimentally evaluate the effectiveness of this representation for machine learning algorithms for classifying biological sequences. In particular, we considered the problem of assigning RNA-Seq reads to the most likely gene from which they were generated. Our results show that fingerprints can provide an effective machine learning interpretable representation, successfully preserving sequence similarity.

Background: Autism spectrum disorders (ASDs) are neurodevelopmental conditions characterized by social and behavioural impairments. In addition to neurological symptoms, ASD subjects frequently suffer from gastrointestinal abnormalities, thus implying a role of the gut microbiota in ASD gastrointestinal pathophysiology. Results: Here, we characterized the bacterial and fungal gut microbiota in a cohort of autistic individuals demonstrating the presence of an altered microbial community structure. A fraction of 90% of the autistic subjects were classified as severe ASDs. We found a significant increase in the Firmicutes/Bacteroidetes ratio in autistic subjects due to a reduction of the Bacteroidetes relative abundance. At the genus level, we observed a decrease in the relative abundance of Alistipes, Bilophila, Dialister, Parabacteroides, and Veillonella in the ASD cohort, while Collinsella, Corynebacterium, Dorea, and Lactobacillus were significantly increased. Constipation has been then associated with different bacterial patterns in autistic and neurotypical subjects, with constipated autistic individuals characterized by high levels of bacterial taxa belonging to Escherichia/Shigella and Clostridium cluster XVIII. We also observed that the relative abundance of the fungal genus Candida was more than double in the autistic than neurotypical subjects, yet due to a larger dispersion of values, this difference was only partially significant. Conclusions: The finding that, besides the bacterial gut microbiota, also the gut mycobiota contributes to the alteration of the intestinal microbial community structure in ASDs opens the possibility for new potential intervention strategies aimed at the relief of gastrointestinal symptoms in ASDs.

Motivated by applications to string processing, we introduce variants of the Lyndon factorization called inverse Lyndon factorizations. Their factors, named inverse Lyndon words, are in a class that strictly contains anti-Lyndon words, that is Lyndon words with respect to the inverse lexicographic order. The Lyndon factorization of a nonempty word w is unique but w may have several inverse Lyndon factorizations. We prove that any nonempty word w admits a canonical inverse Lyndon factorization, named ICFL(w), that maintains the main properties of the Lyndon factorization of w: it can be computed in linear time, it is uniquely determined, and it preserves a compatibility property for sorting suffixes. In particular, the compatibility property of ICFL(w) is a consequence of another result: any factor in ICFL(w) is a concatenation of consecutive factors of the Lyndon factorization of w with respect to the inverse lexicographic order.

The human gut microbiota directly affect human health. Alterations in the composition of commensal bacteria can lead to chronic inflammation also predisposing individuals to fungal infections. Commensal fungi are important in human health and changes in commensal fungal populations have been shown to deeply affect pathologies not directly related to fungi, such as Inflammatory Bowel Diseases. Rett syndrome (RTT) is a neurodegenerative disorder caused by a mutation in MECP2. High proportion of RTT subjects suffer of gastrointestinal disorders, implying a link between RTT and the gut microbiota. We studied the bacterial and fungal gut microbiota of patients affected by RTT by a multilevel approach to understand whether changes in gut microbiota of RTT patients could be associated with GI abnormalities, inflammatory status and cytokine dysregulation previously observed. Our findings revealed that RTT patients harbor a distinct and less diverse bacterial and fungal microbiota compared to healthy subjects in which Bifidobacterium and Candida are the most abundant genera. The immunological responses exerted by RTT yeast isolates in our in vitro cell model suggest that fungi could contribute to the gastrointestinal abnormalities and intestinal inflammation observed in our RTT study cohort.