title: Efficient computation of optimal oligo-RNA binding.
abstract: We present an algorithm that calculates the optimal binding conformation and free energy of two RNA molecules, one or both oligomeric. This algorithm has applications to modeling DNA microarrays, RNA splice-site recognitions and other antisense problems. Although other recent algorithms perform the same calculation in time proportional to the sum of the lengths cubed, O((N1 + N2)3), our oligomer binding algorithm, called bindigo, scales as the product of the sequence lengths, O(N1*N2). The algorithm performs well in practice with the aid of a heuristic for large asymmetric loops. To demonstrate its speed and utility, we use bindigo to investigate the binding proclivities of U1 snRNA to mRNA donor splice sites.
authors.affiliation: Physics Department, Williams College, Williamstown, MA 01267, USA.
authors.forename: Nathan O
authors.initials: NO
authors.lastname: Hodas
authors.forename: Daniel P
authors.initials: DP
authors.lastname: Aalberts
mesh_terms: D000465:Algorithms; D020029:Base Pairing; D001483:Base Sequence; D001665:Binding Sites; D019295:Computational Biology / Q000379:methods*; D009690:Nucleic Acid Conformation; D009843:Oligoribonucleotides / Q000737:chemistry* / Q000378:metabolism; D022821:RNA Splice Sites; D012333:RNA, Messenger / Q000737:chemistry / Q000378:metabolism; D012342:RNA, Small Nuclear / Q000737:chemistry / Q000378:metabolism; D016415:Sequence Alignment; D017423:Sequence Analysis, RNA / Q000379:methods*
chemical_list: D009843:Oligoribonucleotides; D022821:RNA Splice Sites; D012333:RNA, Messenger; D012342:RNA, Small Nuclear; C405483:U1 small nuclear RNA