Article

Free access

Finding similar regions in many strings

Authors:

Ming Li,

Bin Ma,

Lusheng WangAuthors Info & Claims

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

Pages 473 - 482

https://doi.org/10.1145/301250.301376

Published: 01 May 1999 Publication History

PDF eReader

References

[1]

V. Barns, E. Lawlcr and P. Pevzner, Approximation algorithms for multiple sequence alignment, Proc. 8th Ann. Combinatorial Pattern Matching Conf. (CPM'9~I), pp. 43.53~ 1994.

Digital Library

Google Scholar

[2]

A. Ben-Dot, G. Lancta, J. Perone, and R. Ravl, Banishlng bias from consensus sequences, Proc. 8th Ann. Combinatorial Pattern Matching Conf. (CPM'97), pp.247-261,1997

Digital Library

Google Scholar

[3]

Berman, D. Gumucio, R. Hardison~ W. Miller, and N. $tojanovic, A linear-time algorithm for the l-mismatch problem, WADS'97, 1997.

Digital Library

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Crossref

Google Scholar

[7]

M. Frances, A. Litman, On covering problems of codes, Theor. Comput. Syst. 30(1997) 113-119.

Crossref

Google Scholar

[8]

M. Garey and D. Johnson, Computers and Intractability, a guild to the theory of NP-completeness, Freeman, 1979.

Digital Library

Google Scholar

[9]

L. GOsieniec, J. Jansson, and A. Lingas, Efficient approximation algorithms for the Hamming center problem, to appear in SODA '99.

Digital Library

Google Scholar

[10]

D. Gusfield, Efficient methods for multiple sequence alignment with guaranteed error bounds, Bull. Math. Biol., vol. 30, pp. 141-154, 1993.

Crossref

Google Scholar

[11]

D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge Univ. Press, 1997.

Digital Library

Google Scholar

[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.

Google Scholar

[13]

W. t~oeffding, Probability inequalities for sums of bound random variables. J. Amar. Statist. Assoc.,

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Crossref

Google Scholar

[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.

Google Scholar

[18]

K. Lanctot, M. Li, B. Ms, $. Wang, and L. Zhang, Distinguishing string selection problems, to appear in SODA '99.

Digital Library

Google Scholar

[19]

M. Li, P. Vi~/myi, An Introduction to Kolmogoro~ Complexity and Its Applications, Springer, 1993.

Digital Library

Google Scholar

[20]

R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge Univ. Press~ 1995.

Digital Library

Google Scholar

[21]

P. Pevzner, Multiple alignment, communication cost, and graph matching, SIAM J. Applied Math., ~2(1~92), 1~~~-t779.

Digital Library

Google Scholar

[22]

D. S. Prestridge, SIGNAL SCAN 4.0: additional databases and sequence formal:s, (TABIOS (1996) 157-160.

Google Scholar

[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

Google Scholar

[24]

M.A. Roytberg, A search ~or common patterns in many sequences, CABIOS (1992) 57-64.

Google Scholar

[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.

Crossref

Google Scholar

[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.

Google Scholar

[27]

F. Wolfertstetter, K. Frech, G. Herrmann and T. Wemer, CABIOS (1996) 71-80.

Google Scholar

Cited By

View all

Romero RMenichelli CVroland CMarin JLèbre SLecellier CBréhélin L(2024)TFscope: systematic analysis of the sequence features involved in the binding preferences of transcription factorsGenome Biology10.1186/s13059-024-03321-825:1Online publication date: 10-Jul-2024
https://doi.org/10.1186/s13059-024-03321-8
Blum CFesta P(2024)Selected String ProblemsHandbook of Heuristics10.1007/978-3-319-07153-4_58-2(1-21)Online publication date: 2-Aug-2024
https://doi.org/10.1007/978-3-319-07153-4_58-2
Tognon MGiugno RPinello L(2023)A survey on algorithms to characterize transcription factor binding sitesBriefings in Bioinformatics10.1093/bib/bbad156Online publication date: 25-Apr-2023
https://doi.org/10.1093/bib/bbad156
Show More Cited By

Index Terms

Finding similar regions in many strings

Recommendations

Finding Optimum Similar Regions
CISP '08: Proceedings of the 2008 Congress on Image and Signal Processing, Vol. 2 - Volume 02

In this paper we present a novel rotation- and affine-invariant image regions detector, coined OSR (Optimum Similar Regions). The two steps of OSR is: first, segment an image with thresholds based on graph theory, these regions of the segmentation ...
Not So Many Runs in Strings
Language and Automata Theory and Applications

Since the work of Kolpakov and Kucherov in [5,6], it is known that ρ(n), the maximal number of runs in a string, is linear in the length nof the string. A lower bound of $3/(1 + \sqrt{5})n \sim 0.927n$ has been given by Franek ...
Prefix and Suffix Reversals on Strings
SPIRE 2015: Proceedings of the 22nd International Symposium on String Processing and Information Retrieval - Volume 9309

The Sorting by Prefix Reversals problem consists in sorting the elements of a given permutation $$\pi $$ with a minimum number of prefix reversals, i.e. reversals that always imply the leftmost element of $$\pi $$. A natural extension of this problem is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

May 1999

790 pages

ISBN:1581130678

DOI:10.1145/301250

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC99

Sponsor:

SIGACT

STOC99: ACM Symposium on Theory of Computing

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

97
Total Citations
View Citations
925
Total Downloads

Downloads (Last 12 months)78
Downloads (Last 6 weeks)16

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Romero RMenichelli CVroland CMarin JLèbre SLecellier CBréhélin L(2024)TFscope: systematic analysis of the sequence features involved in the binding preferences of transcription factorsGenome Biology10.1186/s13059-024-03321-825:1Online publication date: 10-Jul-2024
https://doi.org/10.1186/s13059-024-03321-8
Blum CFesta P(2024)Selected String ProblemsHandbook of Heuristics10.1007/978-3-319-07153-4_58-2(1-21)Online publication date: 2-Aug-2024
https://doi.org/10.1007/978-3-319-07153-4_58-2
Tognon MGiugno RPinello L(2023)A survey on algorithms to characterize transcription factor binding sitesBriefings in Bioinformatics10.1093/bib/bbad156Online publication date: 25-Apr-2023
https://doi.org/10.1093/bib/bbad156
Garbelini JSanches DPozo A(2022)Expectation Maximization based algorithm applied to DNA sequence motif finder2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870303(1-8)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1109/CEC55065.2022.9870303
Xu SPerkins D(2022)A Heuristic Solution to the Closest String Problem Using Wave Function Collapse TechniquesIEEE Access10.1109/ACCESS.2022.321800310(115869-115883)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3218003
Garbelini JSanches DPozo A(2022)Towards a Better Understanding of Heuristic Approaches Applied to the Biological Motif DiscoveryIntelligent Systems10.1007/978-3-031-21686-2_13(180-194)Online publication date: 19-Nov-2022
https://doi.org/10.1007/978-3-031-21686-2_13
Prosperi MMarini SBoucher C(2021)Fast and exact quantification of motif occurrences in biological sequencesBMC Bioinformatics10.1186/s12859-021-04355-622:1Online publication date: 18-Sep-2021
https://doi.org/10.1186/s12859-021-04355-6
Kaysar MIbrahim Khan M(2019)Chapman-Kolmogorov Relation Based Median String Algorithm for DNA Consensus Classification2019 1st International Conference on Advances in Science, Engineering and Robotics Technology (ICASERT)10.1109/ICASERT.2019.8934582(1-6)Online publication date: May-2019
https://doi.org/10.1109/ICASERT.2019.8934582
Caldonazzo Garbelini JKashiwabara ASanches D(2018)Sequence motif finder using memetic algorithmBMC Bioinformatics10.1186/s12859-017-2005-119:1Online publication date: 3-Jan-2018
https://doi.org/10.1186/s12859-017-2005-1
Blum CFesta P(2018)Selected String ProblemsHandbook of Heuristics10.1007/978-3-319-07124-4_58(1221-1240)Online publication date: 14-Aug-2018
https://doi.org/10.1007/978-3-319-07124-4_58
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Finding Optimum Similar Regions

Not So Many Runs in Strings

Prefix and Suffix Reversals on Strings