Title :
Greedy algorithms for the shortest common superstring that are asymptotically optimal
Author :
Frieze, Alan ; Szpankowski, Wojciech
Author_Institution :
Dept. of Math., Carnegie Mellon Univ., Pittsburgh, PA, USA
fDate :
29 Jun-4 Jul 1997
Abstract :
Various versions of the shortest common superstring (SCS) problem play important roles in data compression and DNA sequencing. For example, in laboratories DNA sequencing is routinely done by sequencing large numbers of relatively short fragments, and then heuristically finding a short common superstring. We assume that the input strings are independently generated, and we adopt a mixing model for the underlying probabilistic model of strings generation
Keywords :
DNA; data compression; entropy; estimation theory; genetics; optimisation; DNA sequencing; Shannon entropy; asymptotically optimal superstring; data compression; greedy algorithms; independently generated input strings; mixing model; probabilistic model; short fragments; shortest common superstring; strings generation; Collaborative work; Computer science; DNA; Data compression; Entropy; Greedy algorithms; Laboratories; Mathematics; Pattern matching;
Conference_Titel :
Information Theory. 1997. Proceedings., 1997 IEEE International Symposium on
Conference_Location :
Ulm
Print_ISBN :
0-7803-3956-8
DOI :
10.1109/ISIT.1997.612954
