|
Internet Electronic Journal of Molecular Design - IEJMD, ISSN 1538-6414, CODEN IEJMAT
| ABSTRACT - Internet Electron. J. Mol. Des. June 2004, Volume 3, Number 6, 361-367 |
Identifying the Largest Common Substructure of RNA Structures
Bo Liao and Tian-ming Wang
Internet Electron. J. Mol. Des. 2004, 3, 361-367
|
Abstract:
The primary structure of a ribonucleic acid (RNA) molecule is
a sequence of nucleotides (bases) over the four-letter alphabet
{A, C, G, U}. The secondary structure of an RNA is a set of
free bases and base pairs formed bonds between A-U and C-G.
For secondary structures, these bonds have been traditionally
assumed to be one-to-one and non-crossing. We consider the
largest common substructure (LCS) between two RNA
molecule structures taking into account the primary and the
secondary structures. We present a dynamic programming
algorithm for identifying the largest common substructure of
two RNA structures. The proposed algorithm solve the LCS
problem in time O(mn).
|