Chromatic kernel and its applications

Hu Ding (), Branislav Stojkovic (), Zihe Chen (), Andrew Hughes (), Lei Xu (), Andrew Fritz (), Nitasha Sehgal (), Ronald Berezney () and Jinhui Xu ()
Additional contact information
Hu Ding: State University of New York at Buffalo
Branislav Stojkovic: State University of New York at Buffalo
Zihe Chen: State University of New York at Buffalo
Andrew Hughes: State University of New York at Buffalo
Lei Xu: State University of New York at Buffalo
Andrew Fritz: State University of New York at Buffalo
Nitasha Sehgal: State University of New York at Buffalo
Ronald Berezney: State University of New York at Buffalo
Jinhui Xu: State University of New York at Buffalo

Journal of Combinatorial Optimization, 2016, vol. 31, issue 3, No 22, 1298-1315

Abstract: Abstract In this paper, we study the following Chromatic kernel (CK) problem: given an $$n$$ n -partite graph (called a chromatic correlation graph) $$G=(V,E)$$ G = ( V , E ) with $$V=V_{1}\bigcup \cdots \bigcup V_{n}$$ V = V 1 ⋃ ⋯ ⋃ V n and each partite set $$V_{i}$$ V i containing a constant number $$\lambda $$ λ of vertices, compute a subgraph $$G[V_{CK}]$$ G [ V C K ] of $$G$$ G with exactly one vertex from each partite set and the maximum number of edges or the maximum total edge weight, if $$G$$ G is edge-weighted (among all such subgraphs). CK is a new problem motivated by several applications and no existing algorithm directly solves it. In this paper, we first show that CK is NP-hard even if $$\lambda =2$$ λ = 2 , and cannot be approximated within a factor of $$16/17$$ 16 / 17 unless P = NP. Then, we present a random-sampling-based PTAS for dense CK. As its application, we show that CK can be used to determine the pattern of chromosome associations in the nucleus for a population of cells. We test our approach by using random and real biological data; experimental results suggest that our approach yields near optimal solutions, and significantly outperforms existing approaches.

Keywords: Graph theory; Approximate algorithms; Random sampling; Biomedical applications (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9824-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:3:d:10.1007_s10878-014-9824-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9824-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().