Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/10995/51252
Title: | The c-fragment longest arc-preserving common subsequence problem |
Authors: | Gorbenko, A. Popov, V. |
Issue Date: | 2012 |
Publisher: | Springer Netherlands |
Citation: | Gorbenko A. The c-fragment longest arc-preserving common subsequence problem / Anna Gorbenko, Vladimir Popov // IAENG International Journal of Computer Science. — 2012. — Vol. 39. — № 3. — P. 231-238. |
Abstract: | Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. In particular, arc-annotated sequences are useful in describing the secondary and tertiary structures of RNA and protein sequences. Structure comparison for RNA and for protein sequences has become a central computational problem bearing many challenging computer science questions. The longest arc-preserving common subsequence problem has been introduced as a framework for studying the similarity of arc-annotated sequences. It is a sound and meaningful mathematical formalization of comparing the secondary structures of molecular sequences. In this paper, we consider two special cases of the longest arc-preserving common subsequence problem, efragment LAPCS (unlimited, plain), c-fragment LAPCS (unlimited, unlimited). In particular, we consider a parameterized version of the 1-fragment LAPCS (unlimited, plain) problem, parameterized by the length l of the desired subsequence. We show W[1]-completeness of the problem. Also, we describe an approach to solve c-fragment LAPCS (unlimited, unlimited). This approach is based on constructing logical models for the problem. |
Keywords: | ARC-ANNOTATION LOGICAL MODELS LONGEST COMMON SUBSEQUENCE PARAMETERIZED COMPLEXITY W[1]-COMPLETE ARC-ANNOTATION COMPUTATIONAL PROBLEM LOGICAL MODELS LONGEST ARC-PRESERVING COMMON SUBSEQUENCES LONGEST COMMON SUBSEQUENCES PARAMETERIZED PARAMETERIZED COMPLEXITY PROTEIN SEQUENCES SECONDARY AND TERTIARY STRUCTURES SECONDARY STRUCTURES STRUCTURAL INFORMATION RNA |
URI: | http://elar.urfu.ru/handle/10995/51252 |
SCOPUS ID: | 84868704018 |
PURE ID: | 1075841 |
ISSN: | 1819-656X |
Appears in Collections: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2-s2.0-84868704018.pdf | 1,4 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.