The Complexity of Some Problems on Subsequences and Supersequences

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

The Complexity of Some Problems on Subsequences and Supersequences

Full text

Pdf (861 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 2 (April 1978) table of contents

Pages: 322 - 336

Year of Publication: 1978

ISSN:0004-5411

Author

David Maier

Department of Electrical Engineering and Computer Science, Princeton University, Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 201, Citation Count: 43

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322063.322075 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. D. Ullman , A. V. Aho , D. S. Hirschberg, Bounds on the Complexity of the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.23 n.1, p.1-12, Jan. 1976 [doi>10.1145/321921.321922]
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	Vaclav Chvatal , David A. Klarner , Donald E. Knuth, Selected combinatorial research problems., Stanford University, Stanford, CA, 1972
	4	CIIVATAI., V, Atqo SANKOFF, D Longest common subsequences for two random sequences STAN-CS-75- 477, Stanford U, Stanford, Cahf., Jan 1975
	5	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	6	DAYHOFF, M.O Computer aids to protein sequence determination. J. Theoret. Btology 8, I (Jan 1965), 97-112.
	7	DAYHOFF, M.O. Computer analysis of protein evoluUon. Scient~ Amer. 221, i (July 1969), 86-95
	8	M. J. Fischer , M. S. Paterson, STRING-MATCHING AND OTHER PRODUCTS, Massachusetts Institute of Technology, Cambridge, MA, 1974
	9	FREDMAN, M.L. On computing length of the longest increasing subsequences Discrete Math 11, 1 (jan. 1975), 29-36.
	10	HIRSCHBERG, D S On finding maximal common subsequences TR-156, Comptr Sc~ Lab, Princeton U, Pnnceton, N J, 1974
	11	D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
	12	Daniel S. Hirschberg, The longest common subsequence problem., 1975
	13	KARP, R.M Reduclblhty among combinatorial problems. In Complexity of Computer Computation, R E Mdler and J.W Thatcher, Eds, Plenum, New York, 1972, pp. 85-103
	14	Robert A. Wagner , Roy Lowrance, An Extension of the String-to-String Correction Problem, Journal of the ACM (JACM), v.22 n.2, p.177-183, April 1975 [doi>10.1145/321879.321880]
	15	MORRIS, J.H., AND PRATT, V R. A linear pattern-matching algorithm. TR-40, Comptr Cir., U of Cahforma, Berkeley, Cahf., June 1970
	16	NEEDLEMAN, S B, AND WUNSCH, C S. A general method apphcable to the search for s~mdantmes m the amino acid sequence of two proteins J. Molecular B~ol 48 (1970), 443-453
	17	SANKOFF, D Matching sequences under delet~on/lnsemon constraints Proc. Nat Acad Set. USA 69, 1 an 1972), 4-6
	18	SANKOFF, D., AND CEDERGREN, R J A test for nucleotlde sequence homology. J Molecular Btol 77 (1973), 159-164.
	19	SELLERS, P H An algorithm for the d~stance between two finite sequences J Combm Theory 16 (1974), 253-258
	20	SZYMANSKI, T.G. A specml case of the maxnnal common subsequence problem. TR-170, Comptr ScL Lab, Princeton U, Princeton, N J., Jan. 1975.
	21	Robert A. Wagner, On the complexity of the Extended String-to-String Correction Problem, Proceedings of seventh annual ACM symposium on Theory of computing, p.218-223, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803771]
	22	Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
	23	WEINER, P Linear pattern matching algorithms Proc 14th Annual Syrup on Switching and Automata Theory, 1973, pp 1-11
	24	C. K. Wong , Ashok K. Chandra, Bounds for the String Editing Problem, Journal of the ACM (JACM), v.23 n.1, p.13-16, Jan. 1976 [doi>10.1145/321921.321923]

CITED BY 43

	R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States
	Sami Khuri , Frederick Stern , Teresa Chiu, Randomness of finite strings: a reconstructive approach, Proceedings of the 1997 ACM symposium on Applied computing, p.527-531, April 1997, San Jose, California, United States
	Z. Wang , P. M. Maurer, Scheduling high-level blocks for functional simulation, Proceedings of the 26th ACM/IEEE conference on Design automation, p.87-90, June 25-28, 1989, Las Vegas, Nevada, United States
	Isidore Rigoutsos , Aris Floratos, Motif discovery without alignment or enumeration (extended abstract), Proceedings of the second annual international conference on Computational molecular biology, p.221-227, March 22-25, 1998, New York, New York, United States
	Ambrose K. Laing , Robert Cypher, Deadlock-free routing in arbitrary networks via the flattest common supersequence method, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.55-66, June 28-July 02, 1998, Puerto Vallarta, Mexico
	F. Hadlock, An efficient algorithm for pattern detection and classification, Proceedings of the 1st international conference on Industrial and engineering applications of artificial intelligence and expert systems, p.645-653, June 1988, Tullahoma, Tennessee, United States
	Paolo Barone , Paola Bonizzoni , Gianluca Delta Vedova , Giancarlo Mauri, An approximation algorithm for the shortest common supersequence problem: an experimental analysis, Proceedings of the 2001 ACM symposium on Applied computing, p.56-60, March 2001, Las Vegas, Nevada, United States
	Robert P. Nix, Editing by example, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.600-621, Oct. 1985
	Robert Nix, Editing by example, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.186-195, January 15-18, 1984, Salt Lake City, Utah, United States
	W. J. Hsu, New algorithms for comparing symbol sequences, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.381-389, December 1987, Dallas, Texas, United States
	Campbell B. Fraser , Robert W. Irving, Approximation algorithms for the shortest common supersequence, Nordic Journal of Computing, v.2 n.3, p.303-325, Fall 1995
	Martin Middendorf , David F. Manlove, Combined super-/substring and super-/subsequence problems, Theoretical Computer Science, v.320 n.2-3, p.247-267, June 14, 2004
	Gaia Nicosia , Gianpaolo Oriolo, An approximate A* algorithm and its application to the SCS problem, Theoretical Computer Science, v.290 n.3, p.2021-2029, 3 January 2003
	Guizhen Yang , I. V. Ramakrishnan , Michael Kifer, On the complexity of schema inference from web pages in the presence of nullable data attributes, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Jeong Seop Sim , Kunsoo Park, The consensus string problem for a metric is NP-complete, Journal of Discrete Algorithms, v.1 n.1, p.111-117, February 2003
	Alessandro Agnetis , Arianna Alfieri , Gaia Nicosia, Part Batching and Scheduling in a Flexible Cell to Minimize Setup Costs, Journal of Scheduling, v.6 n.1, p.87-108, January-February 2003
	Praveen R. Thiagarajan , Guang R. Gao, Visualizing Biosequence Data Using Texture Mapping, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.103, October 28-29, 2002
	Yin-Te Tsai, The constrained longest common subsequence problem, Information Processing Letters, v.88 n.4, p.173-176, 30 November 2003
	Krzysztof Pietrzak, On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems, Journal of Computer and System Sciences, v.67 n.4, p.757-771, December 2003
	John Kececioglu , Dean Starrett, Aligning alignments exactly, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.85-96, March 27-31, 2004, San Diego, California, USA
	Siroos K. Afshar, On the complexity of permutation network design, ACM SIGACT News, v.14 n.3, p.31-35, Summer 1982
	Tatsuya Akutsu , Satoru Miyano, On the approximation of protein threading, Proceedings of the first annual international conference on Computational molecular biology, p.3-8, January 20-23, 1997, Santa Fe, New Mexico, United States
	Francis Y. L. Chin , Alfredo De Santis , Anna Lisa Ferrara , N. L. Ho , S. K. Kim, A simple algorithm for the constrained sequence problems, Information Processing Letters, v.90 n.4, p.175-179, 31 May 2004
	B. J. Oommen , K. Zhang , W. Lee, Numerical Similarity and Dissimilarity Measures Between Two Trees, IEEE Transactions on Computers, v.45 n.12, p.1426-1434, December 1996
	Patricia A. Evans , Andrew D. Smith , H. Todd Wareham, On the complexity of finding common approximate substrings, Theoretical Computer Science, v.306 n.1-3, p.407-430, 5 September 2003
	A. Guénoche, About the design of oligo-chips, Discrete Applied Mathematics, v.147 n.1, p.57-67, 1 April 2005
	Kuo-Si Huang , Chang-Biau Yang , Kuo-Tsung Tseng , Yung-Hsing Peng , Hsing-Yen Ann, Dynamic programming algorithms for the mosaic longest common subsequence problem, Information Processing Letters, v.102 n.2-3, p.99-103, April, 2007
	Ganeshkumar Ganapathy , Barbara Goodson , Robert Jansen , Hai-son Le , Vijaya Ramachandran , Tandy Warnow, Pattern Identification in Biogeography, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.4, p.334-346, October 2006
	François Nicolas , Eric Rivals, Longest common subsequence problem for unoriented and cyclic strings, Theoretical Computer Science, v.370 n.1-3, p.1-18, February, 2007
	Mehmet Ercan Nergiz , Maurizio Atzori , Yücel Saygın , Barıʂ Güç, Towards Trajectory Anonymization: a Generalization-Based Approach, Transactions on Data Privacy, v.2 n.1, p.47-75, April 2009
	Costas S. Iliopoulos , M. Sohel Rahman, New efficient algorithms for the LCS and constrained LCS problems, Information Processing Letters, v.106 n.1, p.13-18, March, 2008
	Xiaonan Ji , James Bailey , Guozhu Dong, Mining minimal distinguishing subsequence patterns with gap constraints, Knowledge and Information Systems, v.11 n.3, p.259-286, April 2007
	Shyong Jian Shyu , Chun-Yuan Tsai, Finding the longest common subsequence for multiple biological sequences by ant colony optimization, Computers and Operations Research, v.36 n.1, p.73-91, January, 2009
	V. Yu. Popov, Multiple genome rearrangement by swaps and by element duplications, Theoretical Computer Science, v.385 n.1-3, p.115-126, October, 2007
	Frédéric Guyon , Alain Guénoche, Comparing bacterial genomes from linear orders of patterns, Discrete Applied Mathematics, v.156 n.8, p.1251-1262, April, 2008
	Kuo-Si Huang , Chang-Biau Yang , Kuo-Tsung Tseng , Hsing-Yen Ann , Yung-Hsing Peng, Efficient algorithms for finding interleaving relationship between sequences, Information Processing Letters, v.105 n.5, p.188-193, February, 2008
	Costas S. Iliopoulos , M. Sohel Rahman, Algorithms for computing variants of the longest common subsequence problem, Theoretical Computer Science, v.395 n.2-3, p.255-267, May, 2008
	Paola Bonizzoni , Gianluca Della Vedova , Riccardo Dondi , Guillaume Fertin , Raffaella Rizzi , Stephane Vialette, Exemplar Longest Common Subsequence, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.4, p.535-543, October 2007
	Takeyuki Tamura , Tatsuya Akutsu, Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.5, p.917-923, May 2007
	Christian Blum , Maria J. Blesa , Manuel López-Ibáñez, Beam search for the longest common subsequence problem, Computers and Operations Research, v.36 n.12, p.3178-3186, December, 2009
	Joong Chae Na , Dong Kyue Kim , Jeong Seop Sim, Finding the longest common nonsuperstring in linear time, Information Processing Letters, v.109 n.18, p.1066-1070, August, 2009
	Orgad Keller , Tsvi Kopelowitz , Moshe Lewenstein, On the longest common parameterized subsequence, Theoretical Computer Science, v.410 n.51, p.5347-5353, November, 2009
	Majid Fozunbal, A subsequence-histogram method for generic vocabulary recognition over deletion channels, Proceedings of the 2009 IEEE international conference on Symposium on Information Theory, p.2557-2561, June 28-July 03, 2009, Coex, Seoul, Korea