SVDSS (Structural Variation Discovery from sample-specific strings) is a new method for discovery of SVs from PacBio HiFi reads that combines and effectively leverages mapping-free, mapping-based and assembly-based methodologies for overall superior SV discovery performance. Although the increased accuracy, there is still room for improvements and most limitations are still not fully solved yet. For instance, long read alignment in repetitive regions of the genome and SVs calling in heterozygous regions are still quite inaccurate. During the Shonan meeting, we aimed to improve long read alignment in repetitive regions of the genome by performing an ad-hoc local realignment that prefers higher consistency around potential variation over higher alignment score. To this aim, we formulated a new computational problem and we discussed different methodologies to solve it.

With the recent advancement of the sequencing technologies and computational capabilities, now it is required to process a large number of reference sequences at the pangenomic scale. For indexing pangenomic graphs represented as (non)deterministic finite automata, computing the co-lexicographical order is an essential procedure. Despite of some remarkable results on particular special cases, there is still room to be improved for general cases, especially for one efficient both from a theoretical and practical point of view. This talk gives a brief survey on the state-of-the-art algorithms for computing co-lexicographical order of automata. In particular, three main techniques covering several important algorithms for deterministic and non-deterministic automata are discussed as well as the future direction of further improvement.

Abstract: NFAs are inherently unordered objects, but they represent regular languages on which one can very naturally define a total order: for example, the co-lexicographic order in which words are compared alphabetically from right to left. In this talk I will show that interesting things happen when one tries to map this total order to the states of an accepting NFA for the language: the resulting order of the states is a partial pre-order whose width p turns out to be an important parameter for NFAs and regular languages. For example, take the classic powerset determinization algorithm for converting an NFA of size n into an equivalent DFA: while a straightforward analysis shows that the size of the resulting DFA is at most $2^n$, we prove that it is actually at most $(n-p+1)*2^p$. This implies that PSPACE-complete problems such as NFA equivalence or universality are actually easy on NFAs of small width p (the case p=1 – total order – is particularly interesting). Another implication of this theory is that we can compress NFAs to just $O(log p)$ bits per transition while supporting fast membership queries in the substring closure of the language.

Quantum algorithms have been established for many basic problems on strings. This work shows that new, faster quantum algorithms are possible when the string is highly compressible. We focus on two popular methods for compression — the Lempel-Ziv77 algorithm (LZ77) and the Run-length-encoded Burrows-Wheeler Transform (RL-BWT), and provide optimal quantum algorithms. We also show an efficient way of constructing a (known) compact index with equivalent capabilities as the suffix tree. This data structure is then applied to numerous problems, such as the longest common substring, finding maximal unique matches, lyndon factorization, etc (see arXiv:2302.07235 for a preliminary version).

The genomes of SARS-CoV-2 are classified into variants, some of which are monitored as variants of concern (e.g. the Delta variant B.1.617.2 or Omicron variant B.1.1.529). Proportions of these variants circulating in a human population are typically estimated by large-scale sequencing of individual patient samples. Sequencing a mixture of SARS-CoV-2 RNA molecules from wastewater provides a cost-effective alternative, but requires methods for estimating variant proportions in a mixed sample. From the modeling point of view, a sequenced sample is a pangenome of SARS-CoV-2 strains which needs to be deconstructed into individual genomes. We will briefly explore a solution to this problem and outline limitations of our current approach and some open problems in this area.

Homologous recombination is a major driver of genetic variation of populations. Massive sequencing efforts enable the study of population genetic variation through large collections of genomic sequences, depending on the context called “haplotype reference panel” or “pangenome”. In search for compact, descriptive, and computationally amendable representations of pangenomes, the theory of founder sequences has recently celebrated a comeback in the form of (elastic) founder graphs that enable linear time construction and indexability. Yet, founder graphs have limited ability to represent structural variation.
The variation graph, an alternative data structure, has gained popularity due to its ability to broadly capture genetic variation, including structural variation. This talk discusses the deep connection between founder and variation graphs with respect to homologous recombination. In particular, we highlight how homologous recombination between non-allelic loci gives rise to structural variation.
Consequently, we propose a computational model that unifies both allelic and non-allelic homologous recombination and discuss open problems arising from this model.

DNA alignment has been a killer app for the FM-index, but aligning DNA reads against a single genome can bias research results and medical diagnoses.  In the past few years we have found ways to FM-index datasets of thousands of genomes, but researchers want the results expressed in terms of compact representations called pangenome graphs.  Hundreds of matches in the dataset may correspond to only one or two matches in the graph.  Given a read, therefore, we would like to find which parts of it match well and where they match in the graph, in time depending on the length of the read and the number of matches in the graph but not on the number of matches in the dataset.

Sunday 19 February

Monday 20 February

Tuesday 21 February

Wednesday 22 February

Thursday 23 February

Friday 24 February