A Python library for bi-cluster editing.
- Task: Given a matrix
weights
with positive and negative weights, transform the bipartite graph induced byweights
into a disjoint collection of bi-cliques (bi-clusters) via edge insertions and deletions, such that the overall transformation cost is minimal. - The node sets of the bipartite graph induced by
weights
are the sets of rows and columns. There is an edge between rowi
and columnk
if and only ifweights[i,k] > 0
. - Deleting an existing edge
(i,k)
incurs costweights[i,k]
. - Inserting a non-existing edge
(i,k)
incurs cost-weights[i,k]
.
- Download and install Gurobi and obtain a license by following the instructions in the installation guide for Linux, Mac OS, or Windows.
- Open a shell and execute
pip install biclustpy
.
After installation, import biclustpy as bp
into your Python application. Then use it as follows:
bp.Algorithm
: Use this class to select the algorithm you want to employ.bp.Algorithm.use_ilp(time_limit, tune)
: Call this function if you want to use Gurobi to solve the ILP formulation suggested in G. F. de Sousa Filho et al (2017): New heuristics for the bicluster editing problem.bp.Algorithm.use_ch(alpha, seed)
: Call this function if you want to use the constructive heuristic suggested in G. F. de Sousa Filho et al (2017): New heuristics for the bicluster editing problem.- More algorithms are following soon.
bp.compute_bi_clusters(weights, algorithm)
: Use this function to solve a bi-cluster editing problem.weights
: The problem instance given as anumpy.array
.algorithm
: The selected algorithm given as abp.Algorithm
object.
bp.save_bi_clusters_as_xml(filename, bi_clusters, obj_val, is_optimal, instance = "")
: Use this function to save the obtained solution as an XML file.filename
: The name of the XML file.bi_clusters
: The bi-clusters returned bybp.compute_bi_clusters
.obj_val
: The objective value of the bi-clusters returned bybp.compute_bi_clusters
.is_optimal
: A flag returned bybp.compute_bi_clusters
that indicates whether the computed bi-clusters are guaranteed to be optimal.instance
: A string that contains information about the problem instance.
import numpy as np
import biclustpy as bp
algorithm = bp.Algorithm()
time_limit = 100
tune = True
algorithm.use_ilp(100, True)
n = 30
m = 40
t = .95
weights = np.random.rand(n, m) - (t * np.ones((n, m)))
bi_clusters, obj_val, is_optimal = bp.compute_bi_clusters(weights, algorithm)
filename = "bi_clusters.xml"
instance = "random instance with 30 rows and 40 columns"
bp.save_bi_clusters_as_xml(filename, bi_clusters, obj_val, is_optimal, instance)
Upon installation, you can run biclustpy
from the command line. Usage:
biclustpy [-h]
(--load input-file | --random num-rows num-cols threshold seed)
[--save output-file] [--alg {ILP,CH}]
[--ilp_options time-limit tune]
More more information, execute biclustpy -h
.
You may use and distribute biclustpy under the terms of the GNU Lesser General Public License.