Distinguishing string selection problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Distinguishing string selection problems

Full text

Pdf (876 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 633 - 642

Year of Publication: 1999

ISBN:0-89871-434-6

Authors

J. Kevin Lanctot	Dept. of Computer Science, University of Waterloo, Waterloo, Ont. N2L 3G1, Canada
Ming Li	Dept. of Computer Science, University of Waterloo, Waterloo, Ont. N2L 3G1, Canada
Bin Ma	Dept. of Computer Science, City University of Hong Kong, Hong Kong
Shaojiu Wang	Pasteur Merieux Connaught Canada, 1755 Steeles Avenue West, Toronto, Ontario, M2R 3T4, Canada
Louxin Zhang	BioInformatics Center, NUS and Kent Ridge Digital Labs, 21 Heng Mui Keng Terrace, Singapore 119613

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

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

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.

	ASE9	Alon, N., Spencer, J., and Erdds, P. (1992), "The Probabilistic Method," Wiley, New York.
	AK95	Edoardo Amaldi , Viggo Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoretical Computer Science, v.147 n.1-2, p.181-210, Aug. 7, 1995 [doi>10.1016/0304-3975(94)00254-G]
	AL+92	Arora, S., Lurid, C., Motwani, It., Sudan, M., and Szegedy, M. (1992), Proof verification and intractability of approximation problems, in FOCS 92, pp. 13-22.
	BL+90	Brown, T., Leonard, G. A., Booth, E. D., and Kneale, G. (1990), Influence of pH on the Conformation and Stability of Mismatch Base-pairs in DNA, J. Mol. Biol. 212, 437-440.
	BL+97	Amir Ben-Dor , Giuseppe Lancia , Jennifer Perone , R. Ravi, Banishing Bias from Consensus Sequences, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.247-261, June 30-July 02, 1997
	CL93	Crooke, S., and Lebleu, B. (editors) (1993), "Antisense Research and Applications," CRC Press Inc, Boca Raton.
	DR+93	Dopazo, J., Rodriguez, A., S~iz, J. C., and Sobrino, F. (1993), Design of primers for PCR amplification of highly variable genomes, CABIOS 9, 123-125.
	Fa74	Fagin, R.. (1974), Generalized first-order spectra and polynomial time recognizable sets, in #Complexity of Computation" (1%. Karp, Ed.), pp. 43-73, AMS, Providence.
	FL97	Frances, M., and Litman, A. (1997) On Covering Problems of Codes, Theory of Computing Systems 30, 113-119.
	GJ79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	GJL99	Leszek Gąsieniec , Jesper Jansson , Andrzej Lingas, Efficient approximation algorithms for the Hamming center problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.905-906, January 17-19, 1999, Baltimore, Maryland, United States
	IS+94	Minoru Ito , Kuniyasu Shimizu , Michio Nakanishi , Akihiro Hashimoto, Polynomial-Time Algorithms for Computing Characteristic Strings, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.274-288, June 05-08, 1994
	HMM96	Hillis, E. M., Moritz, C., and Mable, B. K. (1996), "Molecular Systematics," 2nd ed., Sinauer Associates Inc., Sunderland.
	JT+98	Jiang, T., Trendall, C., Wang, S., Wareham, T., and Zhang, X. (1998) Drug target identification using Gibbs sampling techniques, submitted for publication.
	LF75	Lomant, A. J., and Fresco, J. R. (1975), S#ructural and Energetic Consequences of Noncomplementary Base Oppositions in Nucleic Acid Helices Nucleic Acid Res. and Mol. Bio. 15, 185-218.
	LKT90	Longfellow, C. E., Kierzek, It., and Ttu#er, D. H.(1990), Thermodynamic and Spectroscopic Study of Bulge Loops in Oligoribonucleotides, Biochemi# 29, 278-285.
	LB+91	Lucas, K., Busch, M., MSssinger, S., and Thompson, J. A. (1991), An improved microcomputer program for finding gene- or gene family-specific oligonucleotides suitable as primers for polymerase chain reactions or as probes, CABIOS Z, 525-529.
	MM90	Macario, A., and Macazio, E. (1990), #Gene Probes for Bacteria," Academic Press, San Diego.
	MH90	Mathews, C. K., and van Holde, K.E. (1990), #Biochemistry," Benjamin/Cummings Publishing Company, Inc., Redwood City.
	MNR95	Rajeev Motwani , Joseph Seffi Naor , Prabhakar Raghavan, Randomized approximation algorithms in combinatorial optimization, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	MR95	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	PY91	Papadimitriou, C. H., and Yannakakis, M. (1991), Optimization, approximation and complexity classes, JCSS 43, 425-440.
	PH96	Proutski, V., and Holme, E. C. (1996), Primer Master: a new program for the design and analysis of PCR primers, CABIOS 12, 253-255.
	TSF88	Turner, D. H., Sugimoto, N., and Freier, S. M. (1988), RNA Structure Prediction, Ann. Rev. Biophys. Chem. 17, 167-192.
	We91	Wetmur, J. G. (1991), DNA Probes: Applications of the Principles of Nucleic Acid Hybridization, Critical Rev. in Biochem. and Mol. Bio. 26, 227-259.

CITED BY 11

	Ming Li , Bin Ma , Lusheng Wang, Finding similar regions in many strings, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.473-482, May 01-04, 1999, Atlanta, Georgia, United States
	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
	V. Y. Popov, Note: the approximate period problem for DNA alphabet, Theoretical Computer Science, v.304 n.1-3, p.443-447, 28 July 2003
	Christophe Moan , Irena Rusu, Hard problems in similarity searching, Discrete Applied Mathematics, v.144 n.1-2, p.213-227, 30 November 2004
	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
	J. Kevin Lanctot , Ming Li , Bin Ma , Shaojiu Wang , Louxin Zhang, Distinguishing string selection problems, Information and Computation, v.185 n.1, p.41-55, August 25, 2003
	Giuseppe Lancia, Integer programming models for computational biology problems, Journal of Computer Science and Technology, v.19 n.1, p.60-77, January 2004
	Ming Li , Bin Ma , Lusheng Wang, On the closest string and substring problems, Journal of the ACM (JACM), v.49 n.2, p.157-171, March 2002
	Tatsuya Akutsu , Hideo Bannai , Satoru Miyano , Sascha Ott, On the complexity of deriving position specific score matrices from positive and negative sequences, Discrete Applied Mathematics, v.155 n.6-7, p.676-685, April, 2007
	Leszek Gąsieniec , Jesper Jansson , Andrzej Lingas, Efficient approximation algorithms for the Hamming center problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.905-906, January 17-19, 1999, Baltimore, Maryland, United States
	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