Search

A biclustering problem consists of objects and an attribute vector for each object. Biclustering aims at finding a bicluster—a subset of objects that exhibit similar behavior across a subset of attributes, or vice versa. Biclustering in matrices with binary entries (“0”/“1”) can be simplified into the problem of finding submatrices with entries of “1.” In this paper, we consider a variant of the biclustering problem: thek-submatrix partition of binary matrices problem. The input of the problem contains ann×mmatrix with entries (“0”/“1”) and a constant positive integerk. Thek-submatrix partition of binary matrices problem is to find exactlyksubmatrices with entries of “1” such that theseksubmatrices are pairwise row and column exclusive and each row (column) in the matrix occurs in exactly one of theksubmatrices. We discuss the complexity of thek-submatrix partition of binary matrices problem and show that the problem is NP-hard for anyk≥3by reduction from a biclustering problem in bipartite graphs.

Sorting by short block-moves is one of the several approaches recently used for genome rearrangement, and most of the minimum sorting questions by these approaches have been proved to be NP-complete or NP-hard or even PSPACE-complete. Nevertheless, the complexity of minimum sorting by block-moves remains unsolved, and approximation algorithms for it and polynomial-time algorithms on special permutations for it are continuously devised. This paper gives an exponential-time algorithm of minimum sorting by short block-moves, and verifies its practicability by a set of test data.