Some Approximations for Shortest Common Nonsubsequences and Supersequences

1. Bafna, V., Lawler, E.L., Pevzner, P.A.: Approximation algorithms for multiple sequence alignment. Theoret. Comput. Sci. 182, 233–244 (1997)

   Article  MathSciNet  MATH  Google Scholar 

2. Barone, P., Bonzzoni, P., Vedova, G.D., Mauri, G.: An approximation algorithm for the shortset common supersequence problem: an experimental analysis. In: Proc. of the 2001 ACM Symp. on Applied Comput., Las Vegas, March 11-14, pp. 56–60 (2001)

   Google Scholar 

3. Cotta, C.: Memetic algorithms with partial lamarckism for the shortest common supersequence problem. In: Mira, J., Álvarez, J.R. (eds.) IWINAC 2005, vol. 3562, pp. 84–91. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

4. Cotta, C.: A comparison of evolutionary approaches to the shortest common supersequence problem. In: Cabestany, J., Prieto, A.G., Sandoval, F. (eds.) IWANN 2005, vol. 3512, pp. 50–58. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

5. Ford Jr., L.R., Fulkerson, D.R.: Flows in networks, Princeton, N.Y (1962)

   Google Scholar 

6. Fraser, C.B., Irving, R.W.: Approximation alrorithms for the shortest common supersequence. Nordic J. Comput. 2(3), 303–325 (1995)

   MathSciNet  MATH  Google Scholar 

7. Gusfield, D.: Efficient methods for multiple sequence alignment with guaranteed error bounds. Bull. Math. Biol. 55(1), 141–154 (1993)

   Article  MATH  Google Scholar 

8. Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM J. on Discrete Math. (1992)

   Google Scholar 

9. Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25, 322–336 (1978)

   Article  MathSciNet  MATH  Google Scholar 

10. Middendorf, M.: The shortest common non-subsequence problem is NP-complete. Theoret. Comput. Sci. 108, 365–369 (1993)

    Article  MathSciNet  MATH  Google Scholar 

11. Ning, K., Leong, H.W.: Towards a better solution to the schortest common supersequence problem: the decomposition and reduction algorithm. BMC Bioinformatics 7(suppl. 4), S12 (2006)

    Article  Google Scholar 

12. Pevzner, P.A.: Multiple alignment, communication costs, and graph matching. SIAM J. on Appl. Math. 52, 1763–1779 (1992)

    Article  MathSciNet  MATH  Google Scholar 

13. Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. System Sci. 67, 757–771 (2007)

    Article  MathSciNet  MATH  Google Scholar 

14. Raiha, K.-J., Ukkonen, E.: The shortest common supersequence problem over binary alphabet is NP-complete. Theoret. Comput. Sci. 16, 187–198 (1981)

    Article  MathSciNet  MATH  Google Scholar 

15. Reingold, E.M., Nievergelt, J., Deo, N.: Combinatorial algorithms. Prentice-Hall, Inc., Englewood Cliffs (1977)

    MATH  Google Scholar 

16. Rubinov, A.R., Timkovsky, V.G.: Nonsimilarity combinatorial problems. BioSystems 30, 81–92 (1993); Pevzner, P.A., Gelfand, M.S. (eds.): Computer Genetics, pp. 81–92. Elsevier (1993)

    Google Scholar 

17. Rubinov, A.R., Timkovsky, V.G.: String noninclusion optimization problems. SIAM J. Discrete Math. 11, 456–467 (1998)

    Article  MathSciNet  MATH  Google Scholar 

18. Sankoff, D.: Minimum mutation tree of sequences. SIAM J. Appl. Math. 28, 35–42 (1975)

    Article  MathSciNet  MATH  Google Scholar 

19. Timkovsky, V.G.: Complexity of common subsequnce and supersequence problems and related problems. Kibernetika 5, 1–13 (1989); Cybernetics 25, 565–580 (1990) (English translation)

    Google Scholar 

20. Waterman, M.S., Smith, T.F., Beyer, W.A.: Some biological sequence metrics. Adv. Math. 20, 367–387 (1976)

    Article  MathSciNet  MATH  Google Scholar 

Download references