Affiliations: Institute for Problems of Information Transmission,
Russian Academy of Sciences, GSP-4, 101447 Moscow, Russia | Department of Computer Science and DIMACS, Rutgers
University, 96 Frelinghuysen Road, Piscataway, NJ 68854-3018, USA
Note: [] Corresponding author
Abstract: In this paper we show how several problems in different areas of
data mining and knowledge discovery can be viewed as finding the optimal
covering of a finite set. Many such problems arise in biomedical and
bioinformatics research. For example, protein functional annotation based on
sequence information is an ubiquitous bioinformatics problem. It consists of
finding a set of homolog (high similarity) sequences of known function to a
given amino acid sequence of unknown function from the various annotated
sequence data bases. These can then be used as clues in suggesting further
experimental analysis of the new protein. In the present paper we show that
these optimization problems can be stated as maximizations of submodular
functions on the set of candidate subsets -- a generalization that may be
especially useful when conclusions from data mining need to be interpreted by
human experts. This is common to a number of examples we consider below:
diagnostic hypothesis generation, logical methods of data analysis, conceptual
clustering, and proteins functional annotations.
Keywords: protein functional annotation, medical decision making, set covering causal model, submodular function, optimal algorithm
