The Complexity of Some Problems on Subsequences and Supersequences
- 1 April 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 25 (2), 322-336
- https://doi.org/10.1145/322063.322075
Abstract
The complexity of finding the Longest Common Subsequence (LCS) and the Shortest Common Supersequence (SCS) of an arbRrary number of sequences IS considered We show that the yes/no version of the LCS problem is NP-complete for sequences over an alphabet of size 2, and that the yes/no SCS problem is NP- complete for sequences over an alphabet of size 5Keywords
This publication has 14 references indexed in Scilit:
- Bounds on the Complexity of the Longest Common Subsequence ProblemJournal of the ACM, 1976
- On computing the length of longest increasing subsequencesDiscrete Mathematics, 1975
- A linear space algorithm for computing maximal common subsequencesCommunications of the ACM, 1975
- An Extension of the String-to-String Correction ProblemJournal of the ACM, 1975
- A test for nucleotide sequence homologyJournal of Molecular Biology, 1973
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972
- Matching Sequences under Deletion/Insertion ConstraintsProceedings of the National Academy of Sciences, 1972
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970
- Computer Analysis of Protein EvolutionScientific American, 1969
- Computer aids to protein sequence determinationJournal of Theoretical Biology, 1965