کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420693 683970 2007 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the complexity of deriving position specific score matrices from positive and negative sequences
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the complexity of deriving position specific score matrices from positive and negative sequences
چکیده انگلیسی

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 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 hardness results for deriving multiple PSSMs and related problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issues 6–7, 1 April 2007, Pages 676–685
نویسندگان
, , , ,