Research
Our latest developments focus on pangenome indexing, spaceefficient sequence analysis, alignments on sequencelike structures, and transcript and genome assembly.
Research is mostly carried out with our international collaborators and local colleagues.
Pangenome indexing
An example of our recent developments is an extension of BurrowsWheeler transform to finite automaton representing reference genome together with its common variations among the population (pangenome). This enables a spaceefficient index structure to be constructed to support efficient read alignment to a rich model of the population.
Another way to exploit pangenomic information is to build an index directly on the multiple alignment representing individual genomes. Recently, we have developed LempelZiv indexing approaches suitable for this scenario. We are working on seamless ways to improve variant calling exploiting these indexes.
 Sirén, Välimäki, Mäkinen. Indexing Graphs for Path Queries with Applications in Genome Research. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11(2): 375388, 2014.
 Ferrada, Gagie, Hirvola, Puglisi, Hybrid indexes for repetitive datasets, Philosophical Transactions of the Royal Society A, Volume 372, (2014).
 Travis Gagie and Simon J. Puglisi, Searching and indexing genomic databases via kernelization, Frontiers in Bioengineering and Biotechnology, 3(12) (2015).
 Daniel Valenzuela, Tuukka Norri, Niko Välimäki, Esa Pitkänen, Veli Mäkinen: Towards PanGenome Read Alignment to Improve Variation Calling. BMC Genomics, 19, Article 87, 2018.
 Jarno N. Alanko, Travis Gagie, Gonzalo Navarro, Louisa Seelbach Benkner: Tunneling on Wheeler Graphs. In Proc. DCC 2019.
 Veli Mäkinen, Tuukka Norri: Applying the Positional BurrowsWheeler Transform to allpairs Hamming distance. Inf. Process. Lett. 146: 1719 (2019).
 Tuukka Norri, Bastien Cazaux, Dmitry Kosolobov, Veli Mäkinen: Linear time minimum segmentation enables scalable founder reconstruction. Algorithms for Molecular Biology 14(1): 12:112:15 (2019).
 Massimo Equi, Roberto Grossi, Veli Mäkinen, Alexandru I. Tomescu: On the Complexity of String Matching for Graphs. In Proc. ICALP 2019.
 Bastien Cazaux, Dmitry Kosolobov, Veli Mäkinen, Tuukka Norri: Linear time maximum segmentation problems in column stream model. In Proc. SPIRE 2019. To appear.

Jarno Alanko, Giovanna D'Agostino, Alberto Policriti, Nicola Prezza: Regular Languages meet Prefix Sorting. Accepted to SODA 2020.
Spaceefficient sequence analysis
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 spaceefficient 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.
 Belazzougui, Cunial, Kärkkäinen, Mäkinen. Versatile succinct representations of the bidirectional BurrowsWheeler transform. In Proc. ESA 2013.
 Belazzougui. Linear time construction of compressed text indices in compact space. In Proc. STOC 2014.
 Cunial, Belazzougui. Indexed matching statistics and shortest unique substrings. In Proc. SPIRE 2014.
 Belazzougui, Cunial, Kärkkäinen, Mäkinen. Lineartime string indexing and analysis in small space. Manuscript in submission.
 Alanko, Cunial, Belazzougui, Mäkinen: A framework for spaceefficient read clustering in metagenomic samples. BMC Bioinformatics 18(S3): 4960 (2017).
 Jarno Alanko, Tuukka Norri: Greedy Shortest Common Superstring Approximation in Compact Space. In Proc. SPIRE 2017.
 Fabio Cunial, Jarno Alanko, Djamal Belazzougui: A framework for spaceefficient variableorder Markov models. Bioinformatics. To appear.
Transcript assembly and quantification
The assembly of RNASeq reads can be naturally formulated as a graph theoretic problem of explaining a weighted DAG (directed acyclic graph) with weighted paths. In RECOMBSeq 2013 we gave a polynomialtime solution for a variant of this problem, based on minimumcost network flow. In WABI 2013 we showed that another variant is NPhard, but that it admits an efficient solution based on dynamic programming.
In a later paper, we proposed a unifying problem statement for genomeguided multiassembly problems. Moreover, we gave a more efficient algorithm for this general problem which exploits DAG decompositions based on a new graph parameter (arcwidth). In RECOMBSeq 2014 we investigated different problems which add long read, or pairedend read information to some multiassembly formulations, which are solvable by minimumcost network flow, or NPhard, respectively.
 Tomescu, Kuosmanen, Rizzi, Mäkinen. A Novel MinCost Flow Method for Estimating Transcript Expression with RNASeq. BMC Bioinformatics, 14(Suppl 5):S15 (RECOMBSeq 2013 Supplement).
 Tomescu, Kuosmanen, Rizzi, Mäkinen. A Novel Combinatorial Method for Estimating Transcript Expression with RNASeq: Bounding the Number of Paths. In Proc. WABI 2013.
 Tomescu, Gagie, Popa, Rizzi, Kuosmanen, Mäkinen. Explaining a Weighted DAG with Few Paths for Solving GenomeGuided Multiassembly. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2015.
 Rizzi, Tomescu, Veli Mäkinen. On the Complexity of Minimum Path Cover with Subpath Constraints for MultiAssembly. BMC Bioinformatics, 15(Suppl 9), S5, 2014 (RECOMBseq 2014 supplement).
 Kuosmanen, Norri, Mäkinen. Evaluating Approaches to Find Exon Chains based on Long Reads. Briefings in Bioinformatics, 2017.
 Kuosmanen, Paavilainen, Gagie, Chikhi, Tomescu, Mäkinen. Using Minimum Path Cover to Boost Dynamic Programming on DAGs: CoLinear Chaining Extended. In Proc. RECOMB 2018.
 Mäkinen, Tomescu, Kuosmanen, Paavilainen, Gagie, Chikhi. Sparse Dynamic Programming on DAGs with Small Width. ACM Transaction on Algorithms, 15(2): 29:129:21 (2019).
Recombinationaware sequence alignment
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, motherinherited and fatherinherited 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 pairwise 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.
 Mäkinen, Rahkola. Haploid to diploid alignment for variation calling assessment. BMC Bioinformatics 14(S15): S13, 2013.
 Mäkinen, Valenzuela. Recombinationaware alignment of diploid individuals. BMC Genomics 15(Suppl 6):S15, 2014.
 Mäkinen, Valenzuela. Diploid alignments and haplotyping. In Proc. ISBRA 2015.
 Rizzi, Cairo, Mäkinen, Valenzuela, Tomescu. Hardness of Covering Alignment: Phase Transition in PostSequence Genomics. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 16(1):2330, 2018.
Genome assembly
Many bioinformatics research groups at University of Helsinki have developed genome assembly methods. We have collected these activities into a joint project.