کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333948 | 690060 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of finding emerging patterns
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the complexity of finding emerging patterns On the complexity of finding emerging patterns](/preview/png/10333948.png)
چکیده انگلیسی
Emerging patterns have been studied as a useful type of pattern for the diagnosis and understanding of diseases based on the analysis of gene expression profiles. They are useful for capturing interactions among genes (or other biological entities), for capturing signature patterns for disease subtypes, and deriving potential disease treatment plans, etc. In this paper we study the complexity of finding emerging patterns (with the highest frequency). We first show that the problem is MAX SNP-hard. This implies that polynomial time approximation schemes do not exist for the problem unless P=NP. We then prove that for any constant δ<1, the emerging pattern problem cannot be approximated within ratio 2logδn in polynomial time unless NPâDTIME[2polylogn], where n is the number of positions in a pattern.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 335, Issue 1, 20 May 2005, Pages 15-27
Journal: Theoretical Computer Science - Volume 335, Issue 1, 20 May 2005, Pages 15-27
نویسندگان
Lusheng Wang, Hao Zhao, Guozhu Dong, Jianping Li,