Research is mostly carried out with our international collaborators and local colleagues.
An example of our recent developments is an extension of Burrows-Wheeler transform to finite automaton representing reference genome together with its common variations among the population (pan-genome). This enables a space-efficient index structure to be constructed to support efficient read alignment to a rich model of the population.
Another way to exploit pan-genomic information is to build an index directly on the multiple alignment representing individual genomes. Recently, we have developed Lempel-Ziv indexing approaches suitable for this scenario. We are working on seamless ways to improve variant calling exploiting these indexes.
Jarno Alanko, Giovanna D'Agostino, Alberto Policriti, Nicola Prezza: Regular Languages meet Prefix Sorting. Accepted to SODA 2020.
We consider the classical sequence analysis tasks such as computing maximal repeats, maximal exact matches, maximal unique matches, string kernels, etc. using space within constant factor from the information theoretical minimum and time linear in the input length independent of the alphabet size.
In ESA 2013 we showed that there exists a space-efficient variant of the bidirectional BWT index that can be used for linear time analysis, and in STOC 2014 Belazzougui showed how to build such an index in linear time and small space. That result required randomization, but in the combined extended version of these paper we show that deterministic construction and analysis is feasible within the same bounds, using a variant called unidirectional BWT index. A corollary is that suffix arrays and suffix trees can be built in linear time using sublinear extra space in the output size.
The assembly of RNA-Seq reads can be naturally formulated as a graph theoretic problem of explaining a weighted DAG (directed acyclic graph) with weighted paths. In RECOMB-Seq 2013 we gave a polynomial-time solution for a variant of this problem, based on minimum-cost network flow. In WABI 2013 we showed that another variant is NP-hard, but that it admits an efficient solution based on dynamic programming.
In a later paper, we proposed a unifying problem statement for genome-guided multi-assembly problems. Moreover, we gave a more efficient algorithm for this general problem which exploits DAG decompositions based on a new graph parameter (arc-width). In RECOMB-Seq 2014 we investigated different problems which add long read, or paired-end read information to some multi-assembly formulations, which are solvable by minimum-cost network flow, or NP-hard, respectively.
We have proposed generalizations of the traditional global alignment algorithms for the scenario in which one or two of the input genomes are represented with two strings; namely, mother-inherited and father-inherited chromosomes. These generalizations take into account that individual diploid genomes evolve through a mutation and recombination process, and that predictions through variant calling and haplotype assembly may be erroneous in both dimensions.
Our more general formulation of this alignment problem considers each genome as a DAG. A covering alignment consists of two paths in each DAG that cover all the nodes. The cost is given by the pair-wise edit distance of the strings spelled by these paths. The core problem of finding the optimal covering alignment is still open, but many variants of the setting can be solved efficiently.
We are currently working in applications to evaluate and optimize variant calling and haplotyping algorithms.
Many bioinformatics research groups at University of Helsinki have developed genome assembly methods. We have collected these activities into a joint project.