[en] During the last few years more and more functionalities of RNA have been discovered that were previously thought of being carried out by proteins alone. One of the most striking discoveries was the detection of microRNAs, a class of noncoding RNAs that play an important role in post-transcriptional gene regulation. Large-scale analyses are needed for the still increasingly growing amount of sequence data derived from new experimental technologies. In this paper we present a framework for the detection of the distinctive precursor structure of microRNAS that is based on the well-known Smith-Waterman algorithm. By conducting the computation of the local alignment on a FPGA, we are able to gain a substantial speedup compared to a pure software implementation bringing together supercomputer performance and bioinformatics research. We conducted experiments on real genomic data and we found several new putative hits for microRNA precursor structures.
Disciplines :
Computer science
Author, co-author :
May, Patrick ; Zuse Insitute Berlin > Computer Science Research
Klau, Gunnar W.
Bauer, Markus
Steinke, Thomas
Language :
English
Title :
Accelerated microRNA-Precursor Detection Using the Smith-Waterman Algorithm on FPGAs
Publication date :
2007
Event name :
International Workshop, GCCB 2006
Event place :
Eilat, Israel
Event date :
January 21, 2007
Audience :
International
Main work title :
Distributed, High-Performance and Grid Computing in Computational Biology
Editor :
Dubitzky, Werner
Schuster, Assaf
Sloot, Peterm A.
Schroeder, Michael
Romberg, Mathilde
Publisher :
Springer Berlin Heidelberg, Berlin, Heidelberg, Germany
J. S. Mattick. Challenging the dogma: the hidden layer of non-protein rnas in complex organisms. Bioessays, 25:930-939, 2003.
J. S. Mattick. RNA regulation: a new genetics? Nature Genetics, 5:316-323, 2004.
D. Kampa et al. Novel RNAs identified from an in-depth analysis of the transcriptome of human chromosomes 21 and 22. Genome Res., 14(3):331-42, 2004.
J. M. Johnson, S. Edwards, D. Shoemaker, and E. E. Schadt. Dark matter in the genome: evidence of widespread transcription detected by microarray tiling experiments. Trends Genet., 21(2):93-102, 2005.
T. Imanishi et al. Integrative annotation of 21,037 human genes validated by full-length cDNA clones. PLos Biology, 2:856-875, 2004.
J. M. Cummins et al. The colorectal microRNAome. PNAS, 103(10);3687-3692, 2006.
S. Washietl, I. L. Hofacker, M. Lukasser, A. Huttenhofer, and P. F. Stadler. Mapping of conserved RNA secondary structures predicts thousands of functional non-coding RNAs in the human genome. Nat Biotechnol., 23(11):1383-1390, 2005.
K. Missal, D. Rose, and P. F. Stadler. Non-coding RNAs in ciona intestinalis. Bioinformatics, 21(S2):i77-i78, 2005.
K. Missal et al. Prediction of structured non-coding rnas in the genomes of the nematodes caenorhabditis elegans and caenorhabditis briggsae. J. Exp. Zoolog. B. Mol. Dev. Evol., page Epub ahead of print, 2006.
V. Ambros. The functions of animal microRNAs. Nature, 431:350-355, 2004.
D. P. Bartel. MicroRNAs: genomics, biogenesis, mechanism, and function. Cell, 116:281-297, 2004.
C. S. Sullivan and D. Ganem, MicroRNAs and viral infection, Cell, 20:3-7, 2005.
L. He and G. Hannon. MicroRNAs: small RNAs with a big role in gene regulation. Nat. Rev. Genet, 5:522-531, 2004.
Stefan Washietl, Ivo L. Hofacker, and Peter F. Stadler. Fast and reliable prediction of noncoding RNAs. PNAS, 102(7):2454-2459, 2005.
E Rivas and S R Eddy. Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics, 2, 2001.
S. Zhang, B. Haas, E. Eskin, and V. Bafna. Searching genomes for noncoding RNA using FastR. IEEE/ACM Trans. Comput Biology Bioinform., 2(4):366-379, 2005.
R. Klein and S. Eddy. RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics, 4, 2003.
J. Hertel and P. Stadler. Hairpins in a haystack: Recognizing microRNA precursors in comparative genomics data. In ISMB'06, 2006. To appear.
T. Dezulian, M. Remmert, J. Palatnik, D. Weigel, and D. Huson. Identification of plant microRNA homologs. Bioinformatics, 22(3):359-360, 2006.
X. Wang, J. Zhang, F. Li, J. Gu, T. He, X. Zhang, and Y. Li. MicroRNA identification based on sequence and structure alignment. Bioinformatics, 21(18):3610-3614, 2005.
A. Sewer, N. Paul, P. Landgraf, A. Aravin, S. Pfeffer, M. Brownstein, T. Tuschl, E. van Nimwegen, and M. Zavolan. Identification of clustered microRNAs using an ab initio prediction method. BMC Bioinformatics, 6(1):267, 2005.
T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. J. Mol. Biology, 147:195-197, 1981.
S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. J. Mol. Biol., 215:403-410, 1990.
Active Motif Inc. TimeLogic DeCypher solutions, http://www.timelogic.com/ decypher-algorithms.html.
P. May, M. Bauer, C. Koeberle, and G. W. Klau. A computational approach to microRNA detection. Technical Report, Zuse Institute Berlin, 06-44, 2006.
LiSA-Library for Structural Alignment. http://www.planet-lisa.net.
Ivo L. Hofacker. Vienna RNA secondary structure server. Nucl. Acids Res., 31(13):3429-3431, 2003.
S. Griffiths-Jones, R. J. Grocock, S. van Dongen, A. Bateman, and A. J. Enright. miRBase: microRNA sequences, targets and gene nomenclature. Nucleic Acids Research, 34(Database Issue):D140-D144, 2006.
A. J. Enright, B. John, U. Gaul, T. Tuschl, C. Sander, and D. S. Marks. MicroRNA targets in Drosophila. Genome Biology, 5(1):R1.1-R1.14, 2003.
V. Bafna, H. Tang, and S. Zhang. Consensus folding of unaligned RNA sequences revisited. J. Comput Biol., 13(2):283-295, 2006.
I. Bentwich, A. Avniel, Y. Karov, R. Aharonov, S. Gilad, O. Barad, A. Barzilai, P. Einat, U. Einav, E. Meiri, E. Sharon, Y. Spector, and Z. Bentwich. Identification of hundreds of conserved and nonconserved human microRNAs. Nature Genetics, 37(7):766-770, 2005.
S. Margerm. Cray XD1 Smith Waterman Accelerator (SWA) FPGA Design. PNR-DD-0025 Issue 0.7, Cray inc., December 2005.
S. Margerm. Reconfigurable computing in real-world applications. FPGA and Structured ASIC Journal, February 2006. http://www.fpgajournal.com/ articles_2006/pdf/20060207.cray.pdf.
