Group description

We develop algorithms and data structures for the analysis of genome-scale data. Such data is abundant due to modern molecular biology measurement techniques like high-throughput sequencing. We are especially interested in applications of compressed data structures, that make it possible to analyse the often highly redundant data within the space of their information content. We also study other scalability aspects like distributed computation/storage around genome-scale data.

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 (see WABI 2011). This enables a space-efficient index structure to be constructed to support efficient read alignment to a rich model of the population. Finite automaton representation enables good control over the richness of the model as one can e.g. create paths representing different haplotype blocks, a property not easy to handle using e.g. HMM-based aligners.

The group is a member of Helsinki Institute for Information Technology and Finnish Centre of Excellence in Cancer Genetics Research. For the latter, we aim to tailor our finite automaton Burrows-Wheeler index to enable accurate variation calling on cancer genomics data.

News

• We are co-organizing a challenge on variation calling: Variathon 2013
• Our paper on transcript prediction with RNA-seq accepted to RECOMB-seq! (see below)
• Summer internship positions.
• We used to be SuDS group.

  

People

• Veli Mäkinen, Professor
• Travis Gagie, Postdoctoral Researcher
• Simon Puglisi, Postdoctoral Researcher
• Alexandru Tomescu, Postdoctoral Researcher
• Fabio Cunial, Postdoctoral Researcher
• Djamal Belazzougui, Postdoctoral Researcher
• Rumana Quazi, PhD student
• Anna Kuosmanen, Research Assistant
• Krista Longi, Research Assistant

Software

• geneneralized compressed suffix array for indexing multiple alignment of several reference genomes or reference genome plus known variants. Note: Current construction algorithm requires a lot of resources for genome-scale inputs. We are working on a distributed construction algorithm to alleviate this issue.
• all-against-all suffix/prefix alignment for creating overlap graphs for de novo fragment assembly from short reads. Allows approximate overlaps and works in small space.
• readaligner for mapping (short) DNA reads into reference sequences. This is not as fast as some other Burrows-Wheeler-based aligners, but implements faithfully k-mismatches and k-errors search where some other tools may solve a slighly different or implicitly defined problem.
• See the listing at SuDS group for earlier implementations.

Recent Publications

• A. I. Tomescu, A. Kuosmanen, R. Rizzi, and V. Mäkinen. A Novel Min-Cost Flow Method for Estimating Transcript Expression with RNA-Seq. Accepted to RECOMB-Seq 2013.
  [Implementation]
• V. Mäkinen, L. Salmela, and J. Ylinen. Normalized N50 Assembly Metric using Gap-Restricted Co-Linear Chaining.
  BMC Bioinformatics, 13:255 (3 October 2012).
  [Article online]
  [Implementation]
• Niko Välimäki, and Simon J. Puglisi: Distributed String Mining for High-Throughput Sequencing Data.
  In Proc. 12th International Workshop on Algorithms in Bioinformatics (WABI 2012), Springer, LNCS 7534, pp. 441-452, 2012.
• Simon Gog, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, and Niko Välimäki. Multi-Pattern Matching with Bidirectional Indexes.
  In Proc. 18th Annual International Conference on Computing and Combinatorics (COCOON 2012), Springer, LNCS 7434, pp. 384-395, 2012.
  [Article online]
• Niko Välimäki: Least Random Suffix/Prefix Matches in Output-Sensitive Time.
  In Proc. 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), Springer,
  LNCS 7354, pp. 269-279, 2012.
• Niko Välimäki, Susana Ladra and Veli Mäkinen. Approximate all-pairs suffix/prefix overlaps.
  Information & Computation, 213:49-58, 2012. CPM 2010 Special Issue.
  [Article online]
  [Implementation]
• Travis Gagie, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Leena Salmela, and Jorma Tarhio: Indexed Multi-Pattern Matching.
  In Proc. 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), Springer, LNCS 7256, pp. 399-407, 2012.
  [Article online]
• Markus Heinonen, Niko Välimäki, Veli Mäkinen, and Juho Rousu: Efficient Path Kernels for Reaction Function Prediction.
  In Proc. International Conference on Bioinformatics Models, Methods and Algorithms (BIOINFORMATICS 2012), SciTePress, pp. 202-207, 2012.
  [Preprint]
• Leena Salmela, Veli Mäkinen, Niko Välimäki, Johannes Ylinen, and Esko Ukkonen. Fast Scaffolding with Small Independent Mixed Integer Programs.
  Bioinformatics 27(23): 3259-3265, 2011.
  [Article online]
• Jouni Sirén, Niko Välimäki, and Veli Mäkinen: Indexing Finite Language Representation of Population Genotypes.
  In Proc. WABI 2011, Saarbrücken, Germany, September 5-7, 2011.
  [Article online]
  [Full version]
  [Implementation]
• See the listing at SuDS group for earlier publications.

Visitors and alumni

• Niko Välimäki, PhD student / Postdoctoral Researcher (-December 2012), now at Aaltonen lab
• Jouni Sirén, PhD student / Postdoctoral Researcher (-December 2012), now at University of Chile
• Serikzhan Kazi, Research Assistant (Summer 2011-Summer 2012)
• Johannes Fischer, Postdoc, Karlsruhe Institute of Technology, Germany (August-September 2011) and earlier from LMU München, Germany (June 2007)
• Santeri Pietilä, Research Assistant (Spring/Summer 2011)
• Juha Karjalainen, Research Assistant (Autumn 2010), now PhD student at the University of Groningen.
• Fransisco Claude, PhD Student, University of Waterloo, Canada (June 2010)
• Riku Katainen, Research Assistant (Summer 2008-Summer 2010, image: bottom left), now at Aaltonen lab
• Susana Ladra, PhD student, University of A Coruna, Spain (August - November, 2009)
• Antti Laaksonen, Research Assistant (summer 2009)
• Kashyap Dixit, MSc student, IIT Kanpur, India (May 2006 - July 2006)
• Wolfgang Gerlach, Diploma student, Bielefeld University, Germany (August 2006 - September 2006)

Funding

• Academy of Finland:
  • "Algorithms and data structures for personal genomics", 1.8.2010-31.12.2012.
  • Postdoctoral research fellow position
  • Finnish Centre of Excellence in Cancer Genetics Research
• Helsinki Institute for Information Technology
  • Funded Postdoc position.