Finding similar regions in many strings

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding similar regions in many strings

Full text

Pdf (724 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 473 - 482

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Ming Li	Dept. Comput. Sci., Univ. of Waterloo, Waterloo, Ont. N2L 3G1, Canada
Bin Ma	Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, and Department of Mathematics, Peking University, Beijing 100871, P.R. China
Lusheng Wang	Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 65, Citation Count: 18

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/301250.301376 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	Vineet Bafna , Eugene L. Lawler , Pavel A. Pevzner, Approximation Algorithms for Multiple Sequence Alignment, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.43-53, June 05-08, 1994
	2	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
	3	Nikola Stojanovic , Piotr Berman , Deborah Gumucio , Ross Hardison , Webb Miller, A Linear-Time Algorithm for the 1-Mismatch Problem, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.126-135, August 06-08, 1997
	4	Q. Chan, G. Hertz, G. Stormo, Matrix search 1.0: a computer program that scans DNA sequences for transcriptional elements using a database of weight matrices, CABIOS 11995) 563-566.
	5	J. Dopazo, A. Rodriguez, J. C. Sfiiz, and F. Sobrino, Design of primers for PCR amplification of highly variable ~enomes, CABIOS, 9(1993), 123-125.
	6	Y. M. Fraenkel, Y Mandel, D. Friedberg and H. Margalit, Identification of common motifs in unaligned DNA sequences: applicat:ion to Escherichia coli Lrp regulon, GABIOS, (1995) 379-387.
	7	M. Frances, A. Litman, On covering problems of codes, Theor. Comput. Syst. 30(1997) 113-119.
	8	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
	9	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
	10	D. Gusfield, Efficient methods for multiple sequence alignment with guaranteed error bounds, Bull. Math. Biol., vol. 30, pp. 141-154, 1993.
	11	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	12	G. Hertz and O. $tormo, Identification of consensus pal;terns in unaligned DNA and protein sequences: a large-deviation statistical basis for penalizing gaps. In: Proc. $rd Int'l Conf. Bioinforraatics and Genome Rasaarch (Lira and Cantor, eds.) World Scientific, 1995, pp. 201-216.
	13	W. t~oeffding, Probability inequalities for sums of bound random variables. J. Amar. Statist. Assoc.,
	14	R. Karp, Reducibility among combinatorial problems, in R.E. Miller and J.W. Thatcher (eds), Complexity of Computer Computations, Plenum Press, pp. 85-103. ~972.
	15	Y. V. Kondrakhin, A.E. Kel, N.A. Kolchanov, A.G. Romashchenko, and L. Milanesi, Eutmryotic promoter recognition by binding sites for transcription factors, CABIOS, pp. 477-488, 1995.
	16	C. Lawrence and A. Reilly, An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned blopolymer sequences, Proteins 7(1990) 41-51.
	17	K. Lucas, M. Busch, S. MSssinger and J.A. Thompson, An improved microcomputer program for fmding gene- or gene family-specific oligonucleotides suib able as primers for polymerase chain reactions or as probes, CABIOS, 7(1991), 525-529.
	18	J. Kevin Lanctot , Ming Li , Bin Ma , Shaojiu Wang , Louxin Zhang, Distinguishing string selection problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.633-642, January 17-19, 1999, Baltimore, Maryland, United States
	19	Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag New York, Inc., New York, NY, 1993
	20	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	21	Pavel A. Pevzner, Multiple alignment, communication cost, and graph matching, SIAM Journal on Applied Mathematics, v.52 n.6, p.1763-1779, Dec. 1992 [doi>10.1137/0152101]
	22	D. S. Prestridge, SIGNAL SCAN 4.0: additional databases and sequence formal:s, (TABIOS (1996) 157-160.
	23	V. Proutski and E. C. Holme, Primer Master: a new program for the design and analysis of PCR primers, CA BIOS, 12(1996), 253-255
	24	M.A. Roytberg, A search ~or common patterns in many sequences, CABIOS (1992) 57-64.
	25	G. Stormo, Consensus patterns in DNA, in R.F. DooIittle (ed.), Molecular evolution: computer analysis of protein and nucleic acid sequences, Methods in IEnzyrnology, 183, pp. 211-221, 1990.
	26	G. S~ormo and G.W. Har~zell III, Identifying proteinbinding sites from unaligned DNA fragments. Proc. Natl. Acad. $ci. USA, 88(1991)., 5699-5703.
	27	F. Wolfertstetter, K. Frech, G. Herrmann and T. Wemer, CABIOS (1996) 71-80.

CITED BY 18

	Tatsuya Akutsu , Hiroki Arimura , Shinichi Shimozono, On approximation algorithms for local multiple alignment, Proceedings of the fourth annual international conference on Computational molecular biology, p.1-7, April 2000, Tokyo, Japan
	Uri Keich , Pavel A. Pevzner, Finding motifs in the twilight zone, Proceedings of the sixth annual international conference on Computational biology, p.195-204, April 18-21, 2002, Washington, DC, USA
	Ming Li , Bin Ma , Lusheng Wang, Near optimal multiple alignment within a band in polynomial time, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.425-434, May 21-23, 2000, Portland, Oregon, 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
	Xiaoming Wu , Bo Wang , Changxin Song , Jingzhi Cheng, A combined model and a varied Gibbs sampling algorithm used for motif discovery, Proceedings of the second conference on Asia-Pacific bioinformatics, p.99-104, January 01, 2004, Dunedin, New Zealand
	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
	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
	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
	Dongbo Bu , Ming Li , Shuai Cheng Li , Jianbo Qian , Jinbo Xu, Finding compact structural motifs, Theoretical Computer Science, v.410 n.30-32, p.2834-2839, August, 2009
	Bin Ma , Lusheng Wang , Ming Li, Near optimal multiple alignment within a band in polynomial time, Journal of Computer and System Sciences, v.73 n.6, p.997-1011, September, 2007
	Cláudio N. Meneses , Zhaosong Lu , Carlos A. S. Oliveira , Panos M. Pardalos, Optimal Solutions for the Closest-String Problem via Integer Programming, INFORMS Journal on Computing, v.16 n.4, p.419-429, Fall 2004
	Paul Horton , Wataru Fujibuchi, An upper bound on the hardness of exact matrix based motif discovery, Journal of Discrete Algorithms, v.5 n.4, p.706-713, December, 2007
	Rob LeGrand , Evangelos Markakis , Aranyak Mehta, Some results on approximating the minimax solution in approval voting, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Yong Chen , Guojun Li, An effective algorithm of motif finding problem, International Journal of Bioinformatics Research and Applications, v.4 n.2, p.137-149, May 2008
	Mehmet Kaya, MOGAMOD: Multi-objective genetic algorithm for motif discovery, Expert Systems with Applications: An International Journal, v.36 n.2, p.1039-1047, March, 2009
	Ruqian Lu , Caiyan Jia , Shaofang Zhang , Lusheng Chen , Hongyu Zhang, An Exact Data Mining Method for Finding Center Strings and All Their Instances, IEEE Transactions on Knowledge and Data Engineering, v.19 n.4, p.509-522, April 2007