Paper Title:
An Exact Algorithm for 3-Biclique Vertex Partition
  Abstract

The paper aims to study the problem of biclustering for gene expression data, which arises in the program of characterizing DNA clone libraries, especially in the oligonucleotide fingerprinting of ribosomal RNA genes method. Gene expression data are arranged in data matrices. The goal of biclustering is to find a submatrix, i.e., subset of rows and a subset of columns. If each element of a matrix is 0 or 1, biclustering is closely related to finding bicliques in a bipartite. The k-BVP (short for k biclique vertex partition problem) is to decide whether the vertices of a bipartite can be partitioned into k groups, and each group induce a biclique. 2-BVP can be solved in polynomial time, but it is an open problem whether or not k-BVP is in P for all k3. On the one hand, present an O(2|V|-3) algorithm to decide whether or not a bipartite graph contains a 3 biclique vertex partition. On the other hand, give an algorithm to produce simulation data. The testing results show that the algorithm can find a 3-BVP of a bipartite if there exist a 3-BVP in the bipartite.

  Info
Periodical
Edited by
Zhu Zhilin & Patrick Wang
Pages
189-194
DOI
10.4028/www.scientific.net/AMM.40-41.189
Citation
P. Q. Liu, D. M. Zhu, Q. S. Xie, J. J. Xiao, "An Exact Algorithm for 3-Biclique Vertex Partition", Applied Mechanics and Materials, Vols. 40-41, pp. 189-194, 2011
Online since
November 2010
Export
Price
$32.00
Share

In order to see related information, you need to Login.

In order to see related information, you need to Login.

Authors: Hai Feng Li, Ning Zhang
Chapter 1: Transportation & Service Science
Abstract:Maximal frequent itemsets are one of several condensed representations of frequent itemsets, which store most of the information contained in...
21
Authors: Shu Hua Ma, Jin Kuan Wang, Zhi Gang Liu, Hou Yan Jiang
Chapter 1: Applied Mechanics and Measurement Technology of Detection and Monitoring
Abstract:Data measured and collected by WSNs is often unreliable and a big amount of anomaly data exist. Detecting these anomaly in energy-constrained...
226
Authors: Yu Hong Ma, Gui Long Tian, Xian Li
Chapter 1: Artificial Intelligence, Algorithms and Computation Methods
Abstract:The genetic algorithm is used to investigate the Chinese postman problem with the constraints of working time span and load capacity for...
44
Authors: Xia Ling Zeng
Chapter 4: Electronics and Microelectronics, Embedded and Integrated Systems, Communications, Power and Energy, Electric and Magnetic Systems
Abstract:For multilayer mobile sensor network, the issues of improving sensor network coverage by the use of mobile sensors are studied. A...
1137