Constrained pairwise and center-star sequences alignment problems

Yong Zhang (), Joseph Wun-Tat Chan (), Francis Y. L. Chin (), Hing-Fung Ting (), Deshi Ye (), Feng Zhang () and Jianyu Shi ()
Additional contact information
Yong Zhang: Chinese Academy of Sciences
Joseph Wun-Tat Chan: Hong Kong Baptist University
Francis Y. L. Chin: The University of Hong Kong
Hing-Fung Ting: The University of Hong Kong
Deshi Ye: Zhejiang University
Feng Zhang: Hebei University
Jianyu Shi: Northwestern Polytechnical University

Journal of Combinatorial Optimization, 2016, vol. 32, issue 1, No 6, 79-94

Abstract: Abstract Sequence alignment is a fundamental problem in computational biology, which is also important in theoretical computer science. In this paper, we consider the problem of aligning a set of sequences subject to a given constrained sequence. Given two sequences $$A=a_1a_2\ldots a_n$$ A = a 1 a 2 … a n and $$B=b_1b_2\ldots b_n$$ B = b 1 b 2 … b n with a given distance function and a constrained sequence $$C=c_1c_2\ldots c_k$$ C = c 1 c 2 … c k , our goal is to find the optimal sequence alignment of A and B w.r.t. the constraint C. We investigate several variants of this problem. If $$C=c^k$$ C = c k , i.e., all characters in C are same, the optimal constrained pairwise sequence alignment can be solved in $$O(\min \{kn^2,(t-k)n^2\})$$ O ( min { k n 2 , ( t - k ) n 2 } ) time, where t is the minimum number of occurrences of character c in A and B. If in the final alignment, the alignment score between any two consecutive constrained characters is upper bounded by some value, which is called GB-CPSA, we give a dynamic programming with the time complexity $$O(kn^4/\log n)$$ O ( k n 4 / log n ) . For the constrained center-star sequence alignment (CCSA), we prove that it is NP-hard to achieve the optimal alignment even over the binary alphabet. Furthermore, we show a negative result for CCSA, i.e., there is no polynomial-time algorithm to approximate the CCSA within any constant ratio.

Keywords: Sequence alignment; Dynamic programming; Complexity (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9914-6 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:32:y:2016:i:1:d:10.1007_s10878-015-9914-6

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

DOI: 10.1007/s10878-015-9914-6

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 ().