Approximations and Partial Solutions for the Consensus Sequence Problem
作者： Amihood Amir , Haim Paryenty , Liam Roditty
DOI: 10.1007/978-3-642-24583-1_17
关键词: Linear programming relaxation 、 Discrete mathematics 、 Hamming distance 、 Combinatorics 、 Set (abstract data type) 、 Integral solution 、 Upper and lower bounds 、 Constant (mathematics) 、 Mathematics 、 String (physics)
摘要: The problem of finding the consensus a given set strings is formally defined as follows: S = {s1, . sk}, and constant d, find, if it exists, string s*, such that Hamming distance s* from each does not exceed d. In this paper we study an LP relaxation for problem. We prove additive upper bound, depending only in number k, randomized bounds. show empirical results are much better. also compare our program with some algorithms reported literature, shown to perform well.
springer.com
sci-hub.st 参考文章(16)
Markus Chimani, Sebastian Böcker, Matthias Woste, A closer look at the closest string and closest substring problem algorithm engineering and experimentation. pp. 13- 24 ,(2011)
Christina Boucher, Daniel G. Brown, Stephane Durocher, On the Structure of Small Motif Recognition Instances String Processing and Information Retrieval. pp. 269- 281 ,(2008) , 10.1007/978-3-540-89097-3_26
Nikola Stojanovic, Piotr Berman, Deborah Gumucio, Ross Hardison, Webb Miller, A Linear-Time Algorithm for the 1-Mismatch Problem workshop on algorithms and data structures. pp. 126- 135 ,(1997) , 10.1007/3-540-63307-3_53
Sing-Hoi Sze, Songjian Lu, Jianer Chen, Integrating Sample-Driven and Pattern-Driven Approaches in Motif Finding workshop on algorithms in bioinformatics. pp. 438- 449 ,(2004) , 10.1007/978-3-540-30219-3_37
Jens Gramm, Rolf Niedermeier, Peter Rossmanith, Exact Solutions for CLOSEST STRING and Related Problems international symposium on algorithms and computation. pp. 441- 453 ,(2001) , 10.1007/3-540-45678-3_38
Amir Ben-Dor, Giuseppe Lancia, R. Ravi, Jennifer Perone, Banishing Bias from Consensus Sequences combinatorial pattern matching. pp. 247- 261 ,(1997) , 10.1007/3-540-63220-4_63
Rossmanith, Gramm, Niedermeier, Fixed-parameter algorithms for CLOSEST STRING and related problems Algorithmica. ,vol. 37, pp. 25- 42 ,(2003) , 10.1007/S00453-003-1028-3
Leszek Gąsieniec, Jesper Jansson, Andrzej Lingas, Efficient approximation algorithms for the Hamming center problem symposium on discrete algorithms. pp. 905- 906 ,(1999)
J. Kevin Lanctot, Louxin Zhang, Ming Li, Shaojiu Wang, Bin Ma, Distinguishing string selection problems symposium on discrete algorithms. pp. 633- 642 ,(1999)
Leszek Ga̧sieniec, Jesper Jansson, Andrzej Lingas, Approximation algorithms for Hamming clustering problems Journal of Discrete Algorithms. ,vol. 2, pp. 289- 301 ,(2004) , 10.1016/S1570-8667(03)00079-0