Randomized Fixed-Parameter Algorithms for the Closest String Problem

作     者：Chen, Zhi-Zhong Ma, Bin Wang, Lusheng 

作者机构：Tokyo Denki Univ Div Informat Syst Design Hiki Saitama 3500394 Japan Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：2016年第74卷第1期

页      面：466-484页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Ministry of Education, Science, Sports and Culture of Japan Natural Sciences and Engineering Research Council of Canada [RGPIN 238748] Hong Kong SAR government [CityU 123013] National Foundation of China Grants-in-Aid for Scientific Research Funding Source: KAKEN 

主　　题：The closest string problem Fixed-parameter algorithms Randomized algorithms Computational biology 

摘      要：Given a set of strings of equal length and an integer , the closest string problem (CSP) requires the computation of a string of length such that for each , where is the Hamming distance between and . The problem is NP-hard and has been extensively studied in the context of approximation algorithms and fixed-parameter algorithms. Fixed-parameter algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized fixed-parameter algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their time complexities are also significantly better than the previously best known (deterministic) algorithms.