Bioinformatics Advance Access published online on May 30, 2007
Bioinformatics, doi:10.1093/bioinformatics/btm275
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
PALMA: mRNA to Genome Alignments using Large Margin Algorithms
1 Friedrich Miescher Laboratory, Max Planck Society, Spemannstr. 39, 72076 Tübingen, Germany
2 University of Leipzig, Augustusplatz 10/11, 04109 Leipzig, Germany
3 Fraunhofer FIRST, Kekulèstr. 7, 12489 Berlin, Germany
4 Max Planck Institute for Biological Cybernetics, Spemannstr. 38, 72076 Tübingen, Germany
To whom correspondence should be addressed. Gunnar Rätsch, E-mail: Gunnar.Raetsch{at}tuebingen.mpg.de
 |
Abstract |
|---|
Motivation: 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.
Results: We present a novel approach based on large margin learning that combines accurate plice 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 study the accuracy of alignments of mRNAs containing artificially generated micro-exons to genomic DNA. In a carefully designed experiment, we show that our algorithm accurately identifies the intron boundaries as well as boundaries of the optimal local alignment. It outperforms all other methods: for 5702 artificially shortened EST sequences from C. elegans and human it correctly identifies the intron boundaries in all except two cases. The best other method is a recently proposed method called exalin which misaligns 37 of the sequences. Our method also demonstrates robustness to mutations, insertions and deletions, retaining accuracy even at high noise levels.
Availability: Datasets for training, evaluation and testing, additional results and a stand-alone alignment tool implemented in C++ and python are available at http://www.fml.mpg.de/raetsch/projects/palma.
Associate Editor: Dr. GCBReview2006 Issue
Received on November 9, 2006; revised on May 16, 2007; accepted on May 16, 2007
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  D. V. Lu, R. H. Brown, M. Arumugam, and M. R. Brent Pairagon: a highly accurate, HMM-based cDNA-to-genome aligner Bioinformatics, July 1, 2009; 25(13): 1587 - 1593. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Liang, L. Liu, and G. Ji WebGMAP: a web service for mapping and aligning cDNA sequences to genomes Nucleic Acids Res., July 1, 2009; 37(suppl_2): W77 - W83. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
F. De Bona, S. Ossowski, K. Schneeberger, and G. Ratsch Optimal spliced alignments of short sequence reads Bioinformatics, August 15, 2008; 24(16): i174 - i180. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 G. Zeller, R. M. Clark, K. Schneeberger, A. Bohlen, D. Weigel, and G. Ratsch Detecting polymorphic regions in Arabidopsis thaliana with resequencing microarrays Genome Res., June 1, 2008; 18(6): 918 - 929. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
O. Gotoh A space-efficient and accurate method for mapping and aligning cDNA sequences onto genomic sequence Nucleic Acids Res., May 1, 2008; 36(8): 2630 - 2638. [Abstract] [Full Text] [PDF]
|
|