RNA multiple structural alignment with longest common subsequences

Sergey Bereg (), Marcin Kubica (), Tomasz Waleń () and Binhai Zhu ()
Additional contact information
Sergey Bereg: University of Texas at Dallas
Marcin Kubica: Warsaw University
Tomasz Waleń: Warsaw University
Binhai Zhu: Montana State University

Journal of Combinatorial Optimization, 2007, vol. 13, issue 2, No 6, 179-188

Abstract: Abstract In this paper, we present a new model for RNA multiple sequence structural alignment based on the longest common subsequence. We consider both the off-line and on-line cases. For the off-line case, i.e., when the longest common subsequence is given as a linear graph with n vertices, we first present a polynomial O(n 2) time algorithm to compute its maximum nested loop. We then consider a slightly different problem—the Maximum Loop Chain problem and present an algorithm which runs in O(n 5) time. For the on-line case, i.e., given m RNA sequences of lengths n, compute the longest common subsequence of them such that this subsequence either induces a maximum nested loop or the maximum number of matches, we present efficient algorithms using dynamic programming when m is small.

Keywords: RNA multiple structure alignment; Longest common subsequence; Dynamic programming (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-9020-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:13:y:2007:i:2:d:10.1007_s10878-006-9020-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-9020-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().