The Shortest Common Superstring Problem and Viral Genome Compression

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Ilie, Lucian | Popescu, Cristian

Affiliations: Department of Computer Science University of Western Ontario London, Ontario, N6A 5B7, Canada. E-mails: ilie@csd.uwo.ca; cpopescu@uwo.ca

Abstract: Viruses compress their genome to reduce space. One of the main techniques is overlapping genes. We model this process by the shortest common superstring problem. We give an algorithm for computing optimal solutions which is slow in the number of strings but fast (linear) in their total length. This algorithm is used for a number of viruses with relatively few genes. When the number of genes is larger, we compute approximate solutions using the greedy algorithm which gives an upper bound for the optimal solution. We give also a lower bound for the shortest common superstring problem. The results obtained are then compared with what happens in nature. Remarkably, the compression obtained by viruses is very close to the one achieved by modern computers.

Keywords: Virus, viral genome, genome compression, overlapping genes, shortest common superstring problem, approximate solution, lower bound

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 153-164, 2006