Document Actions

Spliced Alignments for ESTs, cDNAs, and Next-Generation Sequencing Reads

Despite many years of research on how to properly align sequences in the presence of sequencing errors, alternative splicing and micro-exons, the correct alignment of mRNA sequences to genomic DNA is still a challenging task. We use large margin structured output learning to learn parameters which improve the accuracy of alignment tools.

PALMA

We developed a novel approach based on large margin learning that combines accurate splice site predictions with common sequence alignment techniques. By solving a convex optimization problem, our algorithm -- called PALMA -- tunes the parameters of the model such that true alignments score higher than other alignments. We studied the accuracy of alignments of mRNAs containing artificially generated micro-exons to genomic DNA. We showed that our algorithm accurately identifies the intron boundaries as well as boundaries of the optimal local alignment. It outperforms all other methods we compared against. Our method also demonstrates robustness to mutations, insertions and deletions, retaining accuracy even at high noise levels.

The project page can be found here.

QPALMA

Calculating alignments for data stemming from next generation sequencing technologies poses a significant challenge. We developed a novel approach called QPALMA for computing accurate spliced alignments of short sequence reads. Our method takes advantage of the read's quality information as well as computational splice site predictions.

QPALMA is based on a machine learning approach similar to support vector machines. It uses a training set of spliced reads with quality information and known alignments. QPALMA then estimates its parameters to maximize alignment accuracy. In computational experiments we illustrate that the quality information as well as the splice site predictions help to improve the alignment quality.

QPALMA is used in combination with other tools to map massive amounts of sequencing data typically generated by the new technologies.

The project page can be found here.

PALMapper

PALMapper is the combination of QPALMA with the short read alignment tool GenomeMapper. PALMapper dratiscally improves the speed of QPALMA, which can be impractical for large genomes or extremely large introns and still computes both spliced and unspliced alignments of RNA-seq reads at high accuracy by taking advantage of base quality information and splice site predictions. To improve efficiency, we combined it with GenomeMapper that quickly carries out an initial read mapping which will then guide a banded Semi-Global and spliced alignment algorithm that allows for long gaps that correspond to introns. PALMapper considerably reduces time consumption without decreasing accuracy compared to QPALMA.

The project page can be found here.

People specializing in this area

Group Leader

Gunnar Rätsch, Ph.D.

More about Gunnar Rätsch, Ph.D....

Graduate Students

Andre Kahles

The task of mapping RNA-Seq reads back to a genome is far from trivial. Many different algorithms were developed over the past decade. Especially the subgroup of spliced aligners is of great interest for RNA-Seq analysis. I am interested in the performance of the different methods and their alignment behaviour. I further analyse what effect filtering of alignments and the selection of true alignments has to different downstream analyses. More information about this topic is available here

More about Andre Kahles...

Alumnae and Alumni

Fabio De Bona

More about Fabio De Bona...

Geraldine Jean, Ph.D.

I am currently working on the development of PALMapper, a spliced alignment tool for short reads. The first goal was to improve the running time by combining QPALMA with GenomeMapper and by refining the dynamic programming algorithm for spliced alignments in order to efficiently deal with the large amount of data provided by NGS technologies.

More about Geraldine Jean, Ph.D....