Stochastic local search for the Feature Set problem, with applications to microarray data

Article


Albrecht, A. 2006. Stochastic local search for the Feature Set problem, with applications to microarray data. Applied Mathematics and Computation. 183 (2), pp. 1148-1164. https://doi.org/10.1016/j.amc.2006.05.128
TypeArticle
TitleStochastic local search for the Feature Set problem, with applications to microarray data
AuthorsAlbrecht, A.
Abstract

We prove a (m/δ)O(κ) · na time bound for finding minimum solutions Smin of Feature Set problems, where n is the total size of a given Feature Set problem, κ ⩽ ∣Smin∣, m equals the number of non-target features, a is a (relatively small) constant, and 1 − δ is the confidence that the solution is of minimum length. In terms of parameterized complexity of NP-complete problems, our time bound differs from an FPT-type bound by the factor mO(κ) for fixed δ. The algorithm is applied to a prominent microarray dataset: The classification of gene-expression data related to acute myeloid leukaemia (AML) and acute lymphoblastic leukaemia (ALL). From the set of potentially significant features calculated by the algorithm we can identify three genes (D88422, M92287, L09209) that produce zero errors on the test set by using a simple, straightforward evaluation procedure (performing the test on the single gene M84526 produces only one error).

KeywordsFeature Set problem; parameterized complexity; stochastic local search; simulated annealing; gene-expression analysis; microarrays
PublisherElsevier
JournalApplied Mathematics and Computation
ISSN0096-3003
Publication dates
PrintDec 2006
Publication process dates
Deposited08 Nov 2013
Output statusPublished
Digital Object Identifier (DOI)https://doi.org/10.1016/j.amc.2006.05.128
LanguageEnglish
Permalink -

https://repository.mdx.ac.uk/item/847y1

  • 15
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as