A Polynomial Time Approximation Scheme for the Closest Shared Center Problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 65-83 |
| Journal / Publication | Algorithmica |
| Volume | 77 |
| Issue number | 1 |
| Online published | 1 Sept 2015 |
| Publication status | Published - Jan 2017 |
Link(s)
Abstract
Mutation region detection is the first step of searching for a disease gene and has facilitated the identification of several hundred human genes that can harbor mutations leading to a disease phenotype. Recently, the closest shared center problem (CSC) was proposed as a core to solve the mutation region detection problem when the pedigree is not given (Ma et al. in IEEE ACM Trans Comput Biol Bioinform 9(2):372–384, 2012). A ratio-2 approximation algorithm was proposed for the CSC problem in Ma et al. (IEEE ACM Trans Comput Biol Bioinform 9(2):372–384, 2012). In this paper, we will design a polynomial time approximation scheme for this problem.
Research Area(s)
- Approximation algorithms, Closest shared center problem, Haplotype inference, Linear programming, Mutation region detection, Randomized sampling and randomized rounding
Citation Format(s)
A Polynomial Time Approximation Scheme for the Closest Shared Center Problem. / Li, Weidong; Wang, Lusheng; Cui, Wenjuan.
In: Algorithmica, Vol. 77, No. 1, 01.2017, p. 65-83.
In: Algorithmica, Vol. 77, No. 1, 01.2017, p. 65-83.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
