On the complexity of deriving position specific score matrices from positive and negative sequences
作者： Tatsuya Akutsu , Hideo Bannai , Satoru Miyano , Sascha Ott
DOI: 10.1016/J.DAM.2004.10.011
关键词:
摘要: Position-specific score matrices (PSSMs) have been applied to various problems in computational molecular biology. In this paper, we study the following problem: given positive examples (sequences) and negative (sequences), find a PSSM which correctly discriminates between examples. We prove that problem is solved polynomial time if size of bounded by constant. On other hand, NP-hard not bounded. also hardness results for deriving multiple PSSMs related problems.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(20)
Avrim L. Blum, Ronald L. Rivest, Original Contribution: Training a 3-node neural network is NP-complete Neural Networks. ,vol. 5, pp. 117- 127 ,(1992) , 10.1016/S0893-6080(05)80010-3
Tatsuya Akutsu, Mutsunori Yagiura, On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biology international colloquium on automata languages and programming. pp. 832- 843 ,(1998) , 10.1007/BFB0055106
Jack Kyte, Russell F. Doolittle, A simple method for displaying the hydropathic character of a protein Journal of Molecular Biology. ,vol. 157, pp. 105- 132 ,(1982) , 10.1016/0022-2836(82)90515-0
Ming Li, Tao Jiang, On the complexity of learning strings and sequences conference on learning theory. pp. 367- 371 ,(1991) , 10.5555/114836.114870
R.H. Leary, J.B. Rosen, P. Jambeck, An Optimal Structure-Discriminative Amino Acid Index for Protein Fold Recognition Biophysical Journal. ,vol. 86, pp. 411- 419 ,(2004) , 10.1016/S0006-3495(04)74117-X
J. Kevin Lanctot, Louxin Zhang, Ming Li, Shaojiu Wang, Bin Ma, Distinguishing string selection problems symposium on discrete algorithms. pp. 633- 642 ,(1999)
Sean R Eddy, None, Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids ,(1998)
S. Kawashima, H. Ogata, M. Kanehisa, AAindex: Amino Acid Index Database Nucleic Acids Research. ,vol. 27, pp. 368- 369 ,(1999) , 10.1093/NAR/27.1.368
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry ,(1987)
Maricel Kann, Bin Qian, Richard A. Goldstein, Optimization of a new score function for the detection of remote homologs. Proteins. ,vol. 41, pp. 498- 503 ,(2000) , 10.1002/1097-0134(20001201)41:4<498::AID-PROT70>3.0.CO;2-3