Prague Stringology Conference 2011
Mira Abraham and Haim J. Wolfson
Inexact Graph Matching by “Geodesic Hashing” for the Alignment of Pseudoknoted RNA Secondary Structures
| Abstract: |
| Non-coding RNAs are transcripts that do not encode proteins play key roles in many biological processes. The alignment of their secondary structures has become a major tool in RNA functional annotation. Many of the non-coding RNAs contain pseudoknots as a structural motif, which proved to be functionally important. We present HARP, a heuristic algorithm for the pairwise alignment of non-restricted (arbitrary) classes of pseudoknotted RNA secondary structures. HARP applies “geodesic hashing” to perform inexact matching of specially defined reduced RNA secondary structure graphs. The method proved to be efficient both in time and memory and was successfully tested on a benchmark of available experimental structures with known function. A web server is available at http://bioinfo3d.cs.tau.ac.il/HARP/. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |