A Polynomial Time Approximation Scheme for the Closest Shared Center Problem

详细信息    查看全文

• 作者：Weidong Li ; Lusheng Wang ; Wenjuan Cui
• 关键词：Closest shared center problem ; Mutation region detection ; Haplotype inference ; Approximation algorithms ; Linear programming ; Randomized sampling and randomized rounding
• 刊名：Algorithmica
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：77
• 期：1
• 页码：65-83
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
• 出版者：Springer US
• ISSN：1432-0541
• 卷排序：77

文摘

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.