The Shortest Common Superstring Problem and Viral Genome Compression

• Autorzy: Ilie L. , Popescu C.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

virus; viral genome; genome compression; overlapping genes; shortest common superstring problem; approximate solution; lower bound

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 153--164
• Opis fizyczny: tab., bibliogr. 15 poz.

Twórcy

autor

Ilie L.

autor

Popescu C.

• Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada,

Bibliografia

• [1] C. Armen, C. Stein: Improved length bounds for the shortest superstring problem. Proc. 5th Internat. Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 955, Springer-Verlag, Berlin, 1995, 494-505.
• [2] C. Armen, C. Stein: A 2⅔ approximation algorithm for the shortest superstring problem. In Proc. Combinatorial Pattern Matching, Lecture Notes in Comput. Sci. 1075, Springer-Verlag, Berlin, 1996, 87-101.
• [3] A. Blum, T. Jiang, M. Li, J. Tromp, M. Yannakakis: Linear approximation of shortest superstrings. J. Assoc. Comput. Mach., 41 (1994), 630-647.
• [4] D. Breslauer, T. Jiang, Z. Jiang: Rotations of periodic strings and short superstrings. J. Algorithms. 24 (1997), 340-353.
• [5] A.J. Cann: Principles of Molecular Virology. 3rd ed. Elsevier Academic Press, London, San Diego, 2001.
• [6] M. Crochemore,W. Rytter: Jewels of Stringology.World Sci. Pub., Singapore, 2003.
• [7] A. Czumaj, L. Gasieniec, M. Piotrow, W. Rytter: Parallel and sequential approximations of shortest superstrings. In Proc. First Scandinavian Workshop on Algorithm Theory, Lecture Notes in Comput. Sci. 824, Springer-Verlag, Berlin, 1994, 95-106.
• [8] M. Daley, I. McQuillan: Viral gene compression: complexity and verification. In Proc. of CIAA'04, Lecture Notes in Comput. Sci. 3317, Springer, Berlin, 2005, 102-112.
• [9] J. Gallant, D. Maier, J. Storer: On finding minimal length superstrings. Journal of Comput. and Syst. Sci., 20 (1980), 50-58.
• [10] R. Kosaraju, J. Park, C. Stein: Long tours and short superstrings. In Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, 1994, 166-177.
• [11] A. Lesk: Introduction to Bioinformatics. Oxford University Press, Oxford, 2002.
• [12] M. Lothaire: Algebraic Combinatorics on Words. Cambridge Univ. Press, 2002.
• [13] J. Storer: Data Compression: Methods and Theory. Computer Science Press, 1988.
• [14] Z. Sweedyk: A 2 1/2-approximation algorithms for shortest superstring. SIAMJ. Comput., 29 (1999), 954-986.
• [15] S. Teng, F. Yao: Approximating shortest superstrings. In Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, 1993, 158-165.