CUDA Spotlight: Knut Reinert

By Calisa Cole, posted Sept. 25, 2013
Read more CUDA in Action Spotlights

GPU-Accelerated Genomics

This week's Spotlight is on Dr. Knut Reinert. Knut is a professor at Freie Universität in Berlin, Germany, as well as chair of the Algorithms in Bioinformatics group in the Institute of Computer Science.

Knut and his team focus on the development of novel algorithms and data structures for problems in the analysis of biomedical mass data.

In particular, the group develops mathematical models for analyzing large genomic sequences and data derived from mass spectrometry experiments (for example, for detecting differential expression of proteins between normal and diseased samples).

Previously, Knut was at Celera Genomics, where he worked on bioinformatics algorithms and software for the Human Genome Project, which assembled the very first human genome.

This interview is part of the CUDA Spotlight Series.

[Ed. note: On Oct. 22, 2013, Knut will deliver a webinar presentation titled: Intro to SeqAn, an Open-Source C++ Template Library]

---

Q & A with Knut Reinert

NVIDIA: Knut, what is your role at Freie Universität Berlin?
Knut: I am a full professor for algorithmic bioinformatics. Freie Universität has a successful BSc and MSc program in bioinformatics as well as associated graduate schools. My research is centered around developing and implementing efficient algorithms and data structures for bioinformatics problems, mostly in the fields of mass spectrometry based proteomics and sequence analysis (e.g. next generation sequencing (NGS)).

NVIDIA: Tell us about the SeqAn library.
Knut: Before setting up the Algorithmic Bioinformatics group at Freie Universität, I had been working for years at a U.S. company – Celera Genomics in Maryland – where I worked on the assembly of both the Drosophila (fruit fly) and human genomes. A central part of these projects was the development of large software packages containing algorithms for assembly and genome analysis developed by the Informatics Research team at Celera.

Although successful, the endeavor clearly showed the lack of available implementations in sequence analysis, even for standard tasks. Implementations of much needed algorithmic components were either not available, or hard to access in third-party, monolithic software products.

With this experience in mind, and being educated at the Max-Planck Institute for Computer Science in Saarbrücken (the home of very successful software libraries like LEDA and CGAL) I put the development of such a software library high on my research agenda.

The fundamental idea was that the library should be comprehensive for the field of sequence analysis, it should be easy to use, and most of all (because of the tremendous data volumes in genomics, ~3 GB per human genome) be efficiently implemented.

In 2003, Andreas Gogol-Döring joined the Algorithmic Bioinformatics group. Over the next 18 months, lively discussions about goals, different software designs, and the possible content of the library followed, which led to various prototypes that allowed us to verify the design ideas with the corresponding implementations.

Although this approach was rather work-intensive, it led to a lot of insights and finally to the current SeqAn design, which in our opinion, fulfills our initial goals.

In the following years we were able to attract a handful of very talented PhD students who joined the project. In 2006, David Weese and Tobias Rausch (now at EMBL) joined the SeqAn team, followed by Anne-Katrin Emde (now at the New York Genome Center) in 2008. Their help in augmenting the functionality of SeqAn and in implementing algorithms, data types, and providing documentation and tutorials was indispensable in making SeqAn a great product.

NVIDIA: Describe the hardware/software platform currently in use by your lab.
Knut: We have modest needs, since we develop tools and software libraries and do not in general have a lot of data analysis tasks. We have a couple of high memory compute servers (6 to 12 cores, between 48 to 256 GB main memory). In addition we have a compute cluster, with some NVIDIA Tesla K20s in the cluster and some on a dedicated development machine.

NVIDIA: What types of parallel algorithms are being implemented?
Knut: So far we have implemented only the low-hanging fruit, which has worked astonishingly well. The parallelization consists of two parts.

The first was to bring an involved data structure, the FM-index, generically onto the GPU. The FM-index allows fast exact and approximate searches of patterns in genome sized data. It is popular, since it uses a small amount of memory. For example, an enhanced suffix array for the complete human genome (another efficient search index) needs 42 GB of main memory, while an FM-index needs much less. Our new implementation in SeqAn needs only 3.7 GB and hence fits on current GPUs.

Secondly, we programmed a parallel traversal on this index in a generic fashion, which allows the code to run on a multicore as well as on the GPU.

NVIDIA: What approaches have been useful for CUDA development?
Knut: First we made sure that the whole SeqAn library compiles with the CUDA compiler on the GPU. Thus, we could seamlessly compile code in SeqAn on the CPU and the GPU.

Secondly, we took a holistic approach and thought "big." Instead of aiming to speed up only certain aspects of the algorithm, we thought about how we can implement the infrastructure to port ALL our indices to the GPU. The end result is simple and elegant.

NVIDIA: Were any specific GPU-accelerated libraries utilized?
Knut: Yes. We used the device vectors and pointers from Thrust to easily port our data structures to the GPU.

NVIDIA: If you had more computing power, what could you do?
Knut: As mentioned above, our research focuses on developing methods and implementations. I am always excited to learn about new hardware options and think about how to incorporate accelerator code into SeqAn.

NVIDIA: What are the biggest challenges going forward?
Knut: C++ compilers used to exhibit quite different behaviors in the past. This has become much better and we were quite pleased how little effort was required to adapt SeqAn for the CUDA compiler.

We hope that this trend continues, such that compiling of ANSI SeqAn will work even more seamlessly, especially if now the new C++-11 standard will be supported. Another challenge is that most applications have large data volumes, so memory bandwidth is a concern for us.

NVIDIA: What are you most excited about, in terms of advancements over the next decade?
Knut: I think the bioinformatics and computation will play an increasingly important role in the biomedical and healthcare fields. Not only on genome sequences, but in general. Similar to the assembly project at the turn of the millennium, I think the next ten years will bring a paradigm shift in medicine.

NVIDIA: How did you become interested in this field?
Knut: After studying computer science, I was intrigued by the idea of solving certain biological problems by formal means. So I decided to choose a bioinformatics topic for my PhD. Luckily, this choice allowed me to get to know Gene Myers, who at this point in time was a professor in Arizona.

Gene was about to become the head of informatics for Celera Genomics and he persuaded me to join the assembly effort at Celera driven by Craig Venter (well, there was not too much persuasion necessary). This was certainly one of the most exciting times of my life.

After leaving Celera to become a professor in Germany, I started the SeqAn project with the clear goal to parallelize the library at one point.

When Prof. Srinivas Aluru invited me to a HPC workshop in Utah, I sent one of my postdocs who met Jacopo Pantaleoni of NVIDIA there. Since Jacopo lives in Berlin, we started a collaboration and one of my PhD students, Enrico Siragusa, joined NVIDIA for a three-month internship during which he ported the FM-index to run on GPUs.

---

Bio for Dr. Knut Reinert

Knut Reinert received his PhD after training as an algorithmicist at the Max-Planck-Institute for Computer Science in Saarbrücken, Germany. Following this he joined Celera Genomics as a senior scientist. At Celera he worked in the group of Professor Gene Myers and participated in the assembly efforts for the genomes of Drosophila Melanogaster and human (see The Human Genome Project).

Since 2002, Knut Reinert has been a full professor at Freie Universität Berlin. During this time he served as Dean of the Computer Science and Math Department (2008-2010). He is also the vice-speaker of the International Max-Planck Research School for Computational Biology and Scientific Computing and the head of the Bioinformatics Joint Commission between the Department of Mathematics and Computer Science, the Department of Biology, Chemistry and Pharmacy, and the Charité Medical School.

• Education:
• Doctorate (PhD), MPI for Computer Science, Saarbrücken, Germany 1999.
• Graduated with honors from the University of the Saarland with the PhD thesis: "A polyhedral approach to sequence alignment problems" supervised by Prof. Dr. Kurt Mehlhorn.
• MSc in computer science, 1994, University of Saarbrücken under supervision of Prof. Dr. Kurt Mehlhorn.

Relevant Links
http://www.seqan.de

Contact Info
Prof. Dr.-Ing. Knut Reinert
Freie Universität Berlin
Phone/fax: +49 30 838 75 222/218
knut.reinert@fu-berlin (dot) de