Abstract
PSSMs (Position-Specific Score Matrices) have been applied to various problems in Bioinformatics. We study the following problem: given positive examples (sequences) and negative examples (sequences), find a PSSM which correctly discriminates between positive and negative examples. We prove that this problem is solved in polynomial time if the size of a PSSM is bounded by a constant. On the other hand, we prove that this problem is NP-hard if the size is not bounded. We also prove similar results on deriving a mixture of PSSMs.
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
Akutsu, T., Yagiura, M.: On the complexity of deriving score functions from examples for problems in molecular biology. Proc. ICALP’98. Lecture Notes in Computer Science, Vol. 1443. Springer-Verlag, Berlin Heidelberg New York (1998) 832–843
Akutsu, T., Arimura, H., Shimozono, S.: On approximation algorithms for local multiple alignment. Proc. 4th ACM Int. Conf. Computational Molecular Biology (2000) 1–7
Durbin, R., Eddy, S., Krogh, A., Mitchison, G.: Biological Sequence Analysis. Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press (1998)
Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin Heidelberg New York (1987)
Garey, M. R., Johnson, D. S.: Computers and Intractability. Freeman (1979)
Henikoff, S., Henikoff, J. G.: Amino acid substitution matrices from protein blocks. Proc. National Academy of Sciences of the USA 89 (1992) 10915–10919
Jiang, T., Li, M.: On the complexity of learning strings and sequences. Proc. 4th ACM Workshop on Computational Learning Theory (1991) 367–274
Kann, M., Qian, B., Goldstein, R. A.: Optimization of a new score function for detection of remote homologs. Proteins 41 (2000) 498–503
Kyte, J., Doolittle, R. F.: A simple method for displaying the hydropathic character of a protein. J. Molecular Biology 157 (1982) 105–132
Lanctot, K., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string selection problems. Proc. 10th ACM-SIAM Symp. Discrete Algorithms (1999) 633–642
Li, M., Ma, B., Wang, L.: Finding similar regions in many strings. Proc. 31st ACM Symp. Theory of Computing (1999) 473–482
Miyano, S., Shinohara, A., Shinohara, T.: Which classes of elementary formal systems are polynomial-time learnable. Proc. 2nd Workshop on Algorithmic Learning Theory (1991) 139–150
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Akutsu, T., Bannai, H., Miyano, S., Ott, S. (2002). On the Complexity of Deriving Position Specific Score Matrices from Examples. In: Apostolico, A., Takeda, M. (eds) Combinatorial Pattern Matching. CPM 2002. Lecture Notes in Computer Science, vol 2373. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45452-7_15
Download citation
DOI: https://doi.org/10.1007/3-540-45452-7_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43862-5
Online ISBN: 978-3-540-45452-6
eBook Packages: Springer Book Archive