On the Complexity of Deriving Position Specific Score Matrices from Examples
On the Complexity of Deriving Position Specific Score Matrices from Examples
复制标题
论从例子中推导位置特定得分矩阵的复杂性
DOI：
10.1007/3-540-45452-7_15
复制
发表时间：
2002
影响因子：
1.2
通讯作者：
S. Ott
中科院分区：
文献类型：
--
作者：
T. Akutsu;H. Bannai;S. Miyano;S. Ott
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), finda PSSM which correctly discriminates between positive and negative 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.
