[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 :
Sciences informatiques
Auteur, co-auteur :
MAY, Patrick ; Zuse Insitute Berlin > Computer Science Research
Klau, Gunnar W.
Bauer, Markus
Steinke, Thomas
Langue du document :
Anglais
Titre :
Accelerated microRNA-Precursor Detection Using the Smith-Waterman Algorithm on FPGAs
Date de publication/diffusion :
2007
Nom de la manifestation :
International Workshop, GCCB 2006
Lieu de la manifestation :
Eilat, Israël
Date de la manifestation :
January 21, 2007
Manifestation à portée :
International
Titre de l'ouvrage principal :
Distributed, High-Performance and Grid Computing in Computational Biology
Editeur scientifique :
Dubitzky, Werner
Schuster, Assaf
Sloot, Peterm A.
Schroeder, Michael
Romberg, Mathilde
Maison d'édition :
Springer Berlin Heidelberg, Berlin, Heidelberg, Allemagne
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.
