Biology Reference
In-Depth Information
s
(
u
)
s
(
w
)
where 0
<
1
<
min
u,w∈U,s
(
u
)
=
s
(
w
)
{|
−
|}
/
|
U
|
and 0
<
2
<
min
u,w∈U,v
(
u
)
=
v
(
w
)
{|v
(
u
)
− v
(
w
)
|}/|U|
. Note that, another upper bound on
2
is
β
to ensure that the resulting problem has nonnegative
a
ij
values.
As a result, the problem is reduced to selecting a subset
U
⊆
U
such that
u∈U
s
(
u
)
|
<α
+
1
(13.21)
U
|
u∈U
v
(
u
)
|
>β−
2
(13.22)
U
|
which is in the form of (13.13)-(13.14). The reduction is polynomial and (13.21-
13.22) holds true if and only if (13.15-13.16) holds true.
Thus D-CB is
NP
-
complete and the proof is complete.
Corollary 13.1.
Problems (13.10) and (13.11) are
NP
-hard.
Proof.
Problem (13.9) is a special class of Problem (13.10) when
α
j
=0for
j ∈ S
r
. Similarly Problem (13.9) is a special class of Problem (13.11) when
β
j
=1for all
j
∈
S
r
. Hence both (13.10) and (13.11) are
NP
-hard.
13.4. Closing Remarks
The concept of feature selection for consistent biclustering is discussed. The aim
in this setting is to select a subset of features in the original data set such that the
obtained subset of data becomes conditionally biclustering-admitting with respect
to the given classification of training samples. The additive and multiplicative
variations of the problem are considered to extend the possibilities of choosing
the most representative set of features. It is shown that the feature selection for
consistent biclustering is
NP
-hard.
References
[1]
A. Ben-Dor, L. Bruhn, N. Friedman, I. Nachman, M. Schummer, and Z. Yakhini.
Tissue classification with gene expression profiles. In
RECOMB '00: Proceedings
of the fourth annual international conference on Computational molecular biology
,
pages 54-64, New York, NY, USA, 2000. ACM Press.
[2]
A. Ben-Dor, N. Friedman, and Z. Yakhini. Class discovery in gene expression data.
In
RECOMB '01: Proceedings of the fifth annual international conference on Com-
putational biology
, pages 31-38, New York, NY, USA, 2001. ACM Press.
[3]
S. Busygin, O. A. Prokopyev, and P. M. Pardalos. Feature selection for consistent
biclustering.
Journal of Combinatorial Optimization
, 10:7-21, 2005.
Search WWH ::
Custom Search