A computational model for RNA multiple structural alignment |
| |
Authors: | Eugene Davydov Serafim Batzoglou |
| |
Affiliation: | Department of Computer Science, Stanford University, Stanford, CA 94305, USA |
| |
Abstract: | This paper addresses the problem of aligning multiple sequences of noncoding RNA (ncRNA) genes. We approach this problem with the biologically motivated paradigm that scoring of ncRNA alignments should be based primarily on secondary structure rather than nucleotide conservation. We introduce a novel graph theoretic model (NLG) for analyzing algorithms based on this approach, prove that the RNA multiple alignment problem is NP-Complete in this model, and present a polynomial time algorithm that approximates the optimal structure of size S within a factor of O(log2S). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|