Abstract
We consider the problem of aligning a set of sequences subject to a given constrained sequence, which has applications in computational biology. In this paper we show that sequence alignment for two sequences A and B with a given distance function and a constrained sequence of k identical characters (say character c) can be solved in O( min {kn 2,(t − k)n 2}) time, where n is the length of A and B, and t is the minimum number of occurrences of character c in A and B. We also prove that the problem of constrained center-star sequence alignment (CCSA) is NP-hard even over the binary alphabet. Furthermore, for some distance function, we show that no polynomial-time algorithm can approximate the CCSA within any constant ratio.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. Journal of Molecular Biology 215(3), 403–410
Bonizzoni, P., Vedova, G.D.: The complexity of multiple sequence alignment with sp-score that is a metric. Theor. Comput. Sci. 259(1-2), 63–79 (2001)
Chin, F.Y.L., Ho, N.L., Lam, T.W., Wong, P.W.H.: Efficient constrained multiple sequence alignment with performance guarantee. Journal of Bioinformatics and Computational Biology 3(1), 1–18 (2005)
Chin, F.Y.L., Santis, A.D., Ferrara, A.L., Ho, N.L., Kim, S.K.: A simple algorithm for the constrained sequence problems. Information Processing Letters 90, 175–179 (2004)
Gusfield, D.: Efficient methods for multiple sequence alignment with guaranteed error bounds. Bulletin of Methematical Biology 55, 141–154 (1993)
Garey, M., Johnson, D.: Computers and Intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco (1979)
Larkin, M.A., Blackshields, G., Brown, N.P., Chenna, R., McGettigan, P.A., McWilliam, H., Valentin, F., Wallace, I.M., Wilm, A., Lopez, R., Thompson, J.D., Gibson, T.J., Higgins, D.G.: ClustalW and ClustalX version 2. Bioinformatics 23(21), 2947–2948 (2007)
Tang, C.Y., Lu, C.L., Chang, M.D.-T., Tsai, Y.-T., Sun, Y.-J., Chao, K.-M., Chang, J.-M., Chiou, Y.-H., Wu, C.-M., Chang, H.-T., Chou, W.-I.: Constrained multiple sequence alignment tool development and its application to rnase family alignment. Journal of Bioinformatics and Computational Biology 1(2), 267–287 (2003)
Wang, L., Jiang, T.: On the complexity of multiple sequence alignment. Journal of Computational Biology 1(4), 337–348 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Zhang, Y. et al. (2014). On the Complexity of Constrained Sequences Alignment Problems. In: Chen, J., Hopcroft, J.E., Wang, J. (eds) Frontiers in Algorithmics. FAW 2014. Lecture Notes in Computer Science, vol 8497. Springer, Cham. https://doi.org/10.1007/978-3-319-08016-1_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-08016-1_28
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08015-4
Online ISBN: 978-3-319-08016-1
eBook Packages: Computer ScienceComputer Science (R0)