Search

This paper presents a generic framework for the design and comparison of polynomial-time approximation algorithms for MINIMUM STAR BICOLORING. This generic framework is parameterized by algorithms which produce sequences of distance- 2 independent sets. As our main technical result we show that, when the parameterized algorithm produces sequences of distance- 2 independent sets that remove at least Ω (n ϵ) edges during each step, the generic framework produces a polynomial-time approximation algorithm for MINIMUM STAR BICOLORING that is always at least O (n 1 − ϵ / (1 + ϵ) ) of optimal. Under the generic framework, we model two algorithms for MINIMUM STAR BICOLORING from the literature: Complete Direct Cover (CDC) [Hossain and Steihaug, Computing a sparse Jacobian matrix by rows and columns, Optim. Methods Softw. 10 (1998), pp. 33–48] and ASBC [Juedes and Jones, Coloring Jacobians revisited: A new algorithm for star and acyclic bicoloring, Optim. Methods Softw. 27(1–3) (2012), pp. 295–309]. We apply our main result to show approximation upper bounds of O (n 3 / 4) and O (n 2 / 3) , respectively, for these two algorithms. Our approximation upper bound for CDC is the first known approximation analysis for this algorithm. In addition to modelling CDC and ASBC, we use the generic framework to build and analyze three new O (n 2 / 3) approximation algorithms for MINIMUM STAR BICOLORING: MAX-NEIGHBORHOOD, MAX-RATIO c , and LOCAL-SEARCH-k. [ABSTRACT FROM AUTHOR]

Motivation De novo motif discovery algorithms find statistically over-represented sequence motifs that may function as transcription factor binding sites. Current methods often report large numbers of motifs, making it difficult to perform further analyses and experimental validation. The motif selection problem seeks to identify a minimal set of putative regulatory motifs that characterize sequences of interest (e.g. ChIP-Seq binding regions). Results In this study, the motif selection problem is mapped to variants of the set cover problem that are solved via tabu search and by relaxed integer linear programing (RILP). The algorithms are employed to analyze 349 ChIP-Seq experiments from the ENCODE project, yielding a small number of high-quality motifs that represent putative binding sites of primary factors and cofactors. Specifically, when compared with the motifs reported by Kheradpour and Kellis, the set cover-based algorithms produced motif sets covering 35% more peaks for 11 TFs and identified 4 more putative cofactors for 6 TFs. Moreover, a systematic evaluation using nested cross-validation revealed that the RILP algorithm selected fewer motifs and was able to cover 6% more peaks and 3% fewer background regions, which reduced the error rate by 7%. Availability and implementation The source code of the algorithms and all the datasets are available at https://github.com/YichaoOU/Set%5fcover%5ftools. Supplementary information Supplementary data are available at Bioinformatics online. [ABSTRACT FROM AUTHOR]