The k-Feature Set problem is W[2]-complete

摘要

We prove the W[2]-completeness of the feature subset selection problem when the cardinality of the subset is the parameter. Aside from the many applications the problem has in data mining literature, the problem is highly relevant in Computational Biology since it arises in differential gene expression analysis using microarray technologies. It is also related to genetic-based prognosis and regulatory interaction discovery using DNA chip technologies.