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

چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 155, Issues 6–7, 1 April 2007, Pages 676–685
نویسندگان
Tatsuya Akutsu, Hideo Bannai, Satoru Miyano, Sascha Ott,