@inproceedings{068ab55d73384d8ebfe7036482f2370c,
title = "On the complexity of deriving position specific score matrices from examples",
abstract = "PSSMs (Position-Specific Score Matrices) have been applied to various problems in Bioinformatics. We study the following problem: given positive examples (sequences) andnegative examples (sequences), finda PSSM which correctly discriminates between positive andnegative examples. We prove that this problem is solvedin 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.",
author = "Tatsuya Akutsu and Hideo Bannai and Satoru Miyano and Sascha Ott",
year = "2002",
doi = "10.1007/3-540-45452-7_15",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "168--177",
editor = "Alberto Apostolico and Masayuki Takeda",
booktitle = "Combinatorial Pattern Matching - 13th Annual Symposium, CPM 2002, Proceedings",
address = "Germany",
note = "13th Annual Symposium on Combinatorial Pattern Matching, CPM 2002 ; Conference date: 03-07-2002 Through 05-07-2002",
}