Why greed works for shortest common superstring problem Export

@article{citeulike:5797486, abstract = {The shortest common superstring problem (SCS) has been extensively studied for its applications in string compression and DNA sequence assembly. Although the problem is known to be Max-SNP hard, the simple greedy algorithm performs extremely well in practice. To explain the good performance, previous researchers proved that the greedy algorithm is asymptotically optimal on random instances. Unfortunately, the practical instances in DNA sequence assembly are very different from the random instances. In this paper we explain the good performance of the greedy algorithm by using the smoothed analysis. We show that, for any given instance I of SCS, the average approximation ratio of the greedy algorithm on a small random perturbation of I is 1+ o (1) . The perturbation defined in the paper is small and naturally represents the mutations of the DNA sequence during evolution. Due to the existence of the uncertain nucleotides in the output of a DNA sequencing machine, we also proposed the shortest common superstring with wildcards problem (SCSW). We prove that in the worst case SCSW cannot be approximated within the ratio n 1/7− , while the greedy algorithm still has 1+ o (1) smoothed approximation ratio.}, author = {Ma, Bin}, citeulike-article-id = {5797486}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.tcs.2009.09.014}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0304397509006410}, day = {15}, doi = {10.1016/j.tcs.2009.09.014}, issn = {03043975}, journal = {Theoretical Computer Science}, keywords = {algorithm, assembly, greed, np-complete, scs}, month = {September}, posted-at = {2009-10-16 04:38:35}, priority = {2}, title = {Why greed works for shortest common superstring problem}, url = {http://dx.doi.org/10.1016/j.tcs.2009.09.014}, year = {2009} }

TY - JOUR ID - citeulike:5797486 L3 - citeulike-article-id:5797486 N2 - The shortest common superstring problem (SCS) has been extensively studied for its applications in string compression and DNA sequence assembly. Although the problem is known to be Max-SNP hard, the simple greedy algorithm performs extremely well in practice. To explain the good performance, previous researchers proved that the greedy algorithm is asymptotically optimal on random instances. Unfortunately, the practical instances in DNA sequence assembly are very different from the random instances. In this paper we explain the good performance of the greedy algorithm by using the smoothed analysis. We show that, for any given instance I of SCS, the average approximation ratio of the greedy algorithm on a small random perturbation of I is 1+ o (1) . The perturbation defined in the paper is small and naturally represents the mutations of the DNA sequence during evolution. Due to the existence of the uncertain nucleotides in the output of a DNA sequencing machine, we also proposed the shortest common superstring with wildcards problem (SCSW). We prove that in the worst case SCSW cannot be approximated within the ratio n 1/7− , while the greedy algorithm still has 1+ o (1) smoothed approximation ratio. JF - Theoretical Computer Science SN - 03043975 TI - Why greed works for shortest common superstring problem KW - algorithm KW - assembly KW - greed KW - np-complete KW - scs AU - Ma, Bin PY - 2009/09/15/ UR - http://dx.doi.org/10.1016/j.tcs.2009.09.014 ER -