Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Mattick, J.S.: Challenging the dogma: The hidden layer of non-protein rnas in complex organisms. Bioessays 25, 930–939 (2003)
Mattick, J.S.: RNA regulation: A new genetics? Nature Genetics 5, 316–323 (2004)
Kampa, D. et al.: Novel RNAs identified from an in-depth analysis of the transcriptome of human chromosomes 21 and 22. Genome Res. 14(3), 331–342 (2004)
Johnson, J.M., Edwards, S., Shoemaker, D., Schadt, E.E.: Dark matter in the genome: evidence of widespread transcription detected by microarray tiling experiments. Trends Genet. 21(2), 93–102 (2005)
Imanishi, T. et al.: Integrative annotation of 21,037 human genes validated by full-length cDNA clones. PLos Biology 2, 856–875 (2004)
Cummins, J.M. et al.: The colorectal microRNAome. PNAS 103(10), 3687–3692 (2006)
Washietl, S., Hofacker, I.L., Lukasser, M., Huttenhofer, A., Stadler, P.F.: Mapping of conserved RNA secondary structures predicts thousands of functional noncoding RNAs in the human genome. Nat. Biotechnol 23(11), 1383–1390 (2005)
Missal, K., Rose, D., Stadler, P.F.: Non-coding RNAs in ciona intestinalis. Bioinformatics 21(S2), 77–78 (2005)
Missal, K. 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)
Ambros, V.: The functions of animal microRNAs. Nature 431, 350–355 (2004)
Bartel, D.P.: MicroRNAs: genomics, biogenesis, mechanism, and function. Cell 116, 281–297 (2004)
Sullivan, C.S., Ganem, D.: MicroRNAs and viral infection. Cell 20, 3–7 (2005)
He, L., Hannon, G.: MicroRNAs: small RNAs with a big role in gene regulation. Nat. Rev. Genet. 5, 522–531 (2004)
Washietl, S., Hofacker, I.L., Stadler, P.F.: Fast and reliable prediction of noncoding RNAs. PNAS 102(7), 2454–2459 (2005)
Rivas, E., Eddy, S.R.: Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics 2 (2001)
Zhang, S., Haas, B., Eskin, E., Bafna, V.: Searching genomes for noncoding RNA using FastR. IEEE/ACM Trans. Comput. Biology Bioinform 2(4), 366–379 (2005)
Klein, R., Eddy, S.: RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics 4 (2003)
Hertel, J., Stadler, P.: Hairpins in a haystack: Recognizing microRNA precursors in comparative genomics data. In: ISMB’06, To appear (2006)
Dezulian, T., Remmert, M., Palatnik, J., Weigel, D., Huson, D.: Identification of plant microRNA homologs. Bioinformatics 22(3), 359–360 (2006)
Wang, X., Zhang, J., Li, F., Gu, J., He, T., Zhang, X., Li, Y.: MicroRNA identification based on sequence and structure alignment. Bioinformatics 21(18), 3610–3614 (2005)
Sewer, A., Paul, N., Landgraf, P., Aravin, A., Pfeffer, S., Brownstein, M., Tuschl, T., van Nimwegen, E., Zavolan, M.: Identification of clustered microRNAs using an ab initio prediction method. BMC Bioinformatics 6(1), 267 (2005)
Smith, T.F., Waterman, M.S.: Identification of common molecular subsequences. J. Mol. Biology 147, 195–197 (1981)
Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: 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
May, P., Bauer, M., Koeberle, C., Klau, G.W.: A computational approach to microRNA detection. Technical Report, Zuse Institute Berlin, 06-44 (2006)
LiSA—Library for Structural Alignment, http://www.planet-lisa.net
Hofacker, I.L.: Vienna RNA secondary structure server. Nucl. Acids Res. 31(13), 3429–3431 (2003)
Griffiths-Jones, S., Grocock, R.J., van Dongen, S., Bateman, A., Enright, A.J.: miRBase: microRNA sequences, targets and gene nomenclature. Nucleic Acids Research 34(Database Issue), D140–D144 (2006)
Enright, A.J., John, B., Gaul, U., Tuschl, T., Sander, C., Marks, D.S.: MicroRNA targets in Drosophila. Genome Biology 5(1), R1.1–R1.14 (2003)
Bafna, V., Tang, H., Zhang, S.: Consensus folding of unaligned RNA sequences revisited. J. Comput. Biol. 13(2), 283–295 (2006)
Bentwich, I., Avniel, A., Karov, Y., Aharonov, R., Gilad, S., Barad, O., Barzilai, A., Einat, P., Einav, U., Meiri, E., Sharon, E., Spector, Y., Bentwich, Z.: Identification of hundreds of conserved and nonconserved human microRNAs. Nature Genetics 37(7), 766–770 (2005)
Margerm, S.: Cray XD1 Smith Waterman Accelerator (SWA) FPGA Design. PNR-DD-0025 Issue 0.7, Cray inc. (December 2005)
Margerm, S.: Reconfigurable computing in real-world applications. FPGA and Structured ASIC Journal, http://www.fpgajournal.com/articles_2006/pdf/20060207_cray.pdf (February 2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
May, P., Klau, G.W., Bauer, M., Steinke, T. (2007). Accelerated microRNA-Precursor Detection Using the Smith-Waterman Algorithm on FPGAs. In: Dubitzky, W., Schuster, A., Sloot, P.M.A., Schroeder, M., Romberg, M. (eds) Distributed, High-Performance and Grid Computing in Computational Biology. GCCB 2007. Lecture Notes in Computer Science(), vol 4360. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69968-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-69968-2_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69841-8
Online ISBN: 978-3-540-69968-2
eBook Packages: Computer ScienceComputer Science (R0)