• Stochastic local search for th...

Result: Stochastic local search for the FEATURE SET problem, with applications to microarray data

Title:
Stochastic local search for the FEATURE SET problem, with applications to microarray data
Authors:
ALBRECHT, Andreas A
Source:
Applied mathematics and computation. 183(2):1148-1164
Publisher Information:
New York, NY: Elsevier, 2006.
Publication Year:
2006
Physical Description:
print, 25 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Analyse numérique. Calcul scientifique, Numerical analysis. Scientific computation, Analyse numérique, Numerical analysis, Méthodes numériques en programmation mathématique, optimisation et calcul variationnel, Numerical methods in mathematical programming, optimization and calculus of variations, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Optimisation. Problèmes de recherche, Optimization. Search problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme, Algorithm, Algoritmo, Estimation erreur, Error estimation, Estimación error, Expression génique, Gene expression, Expresión genética, Mathématiques appliquées, Applied mathematics, Matemáticas aplicadas, Problème NP complet, NP complete problem, Problema NP completo, Problème recherche, Search problem, Problema investigación, Recuit simulé, Simulated annealing, Recocido simulado, Solution bornée, Bounded solution, Solución acotada, Temps minimal, Minimum time, Tiempo mínimo, Complexité paramétrisée, Parameterized complexity, Problème ensemble caractéristiques, FEATURE SET problem, Puce à ADN, Microarray, Recherche stochastique, Gene-expression analysis, Microarrays, Stochastic local search
Document Type:
Academic journal Article
File Description:
text
Language:
English
Author Affiliations:
University of Hertfordshire, School of Computer Science, Hatfield, College Lane, Herts AL10 9AB, United Kingdom
ISSN:
0096-3003
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18442263
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics

Operational research. Management
Accession Number:
edscal.18442263
Database:
PASCAL Archive

Further Information

We prove a (m/δ)O(K) · na time bound for finding minimum solutions Smin of FEATURE SET problems, where n is the total size of a given FEATURE SET problem, K ≤ |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(K) 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).