|
Published Articles >> Table of Contents >> Abstract
28th Annual International Computer Software and Applications Conference - Workshops and Fast Abstracts - (COMPSAC'04)
pp. 126-129
On the Complexity of Finding Emerging Patterns
Lusheng Wang, City University of Hong Kong
Hao Zhao, City University of Hong Kong
Guozhu Dong, Wright State University
Jianping Li, Yunnan University and City University of Hong Kong
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CMPSAC.2004.1342691
Send link to a friend
| Abstract |
|
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 SNPhard.
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 2^{\log ^\delta n} in polynomial time unless
NP \subseteq DTIME[2^{poly\log n}], where n is
the number of positions in a pattern.
|
 Additional Information
|
Citation:
Lusheng Wang, Hao Zhao, Guozhu Dong, Jianping Li,
"On the Complexity of Finding Emerging Patterns,"
compsac,
pp. 126-129,
28th Annual International Computer Software and Applications Conference - Workshops and Fast Abstracts - (COMPSAC'04),
2004
|
|
