Article

Free access

Distinguishing string selection problems

Authors:

J. Kevin Lanctot,

Ming Li,

Bin Ma,

Shaojiu Wang,

Louxin ZhangAuthors Info & Claims

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

Pages 633 - 642

Published: 01 January 1999 Publication History

PDF eReader

References

[1]

Alon, N., Spencer, J., and Erdds, P. (1992), "The Probabilistic Method," Wiley, New York.

Google Scholar

[2]

Amaldi, E., and Kann, V. (1995), The complexity and approximabiIity of finding maximum feasible subsystems of linear relations, Theoret. Comput. Science 147, 1.81-210.

Digital Library

Google Scholar

[3]

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.

Google Scholar

[4]

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.

Google Scholar

[5]

Ben-Dor, A., Lancia, G., Perone, J., and Ravi R. (1997), Banishing Bias from Consensus Sequences, in "Combinatorial Pattern Matching, 8th Annual Symposium," pp. 247-261.

Digital Library

Google Scholar

[6]

Crooke, S., and Lebleu, B. (editors) (1993), "Antisense Research and Applications," CRC Press Inc, Boca Raton.

Google Scholar

[7]

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.

Google Scholar

[8]

Fagin, R. (1974), Generalized first-order spectra and polynomial time recognizable sets, in #Complexity of Computation" (1%. Karp, Ed.), pp. 43-73, AMS, Providence.

Google Scholar

[9]

Frances, M., and Litman, A. (1997) On Covering Problems of Codes, Theory of Computing Systems 30, 113-119.

Google Scholar

[10]

Gamey, M., and Johnson, D. (1979), "Computers and Intractability: a guide to the theory of NP-completeness," W.H. Freeman, San Francisco.

Digital Library

Google Scholar

[11]

G#sieniec, L., Jansson, J., and Lingas, A., (1999) Efficient Approximation Algorithms for the Hamming Center Problem, to appear in SODA'99.

Digital Library

Google Scholar

[12]

Ito, M., Shimizu, K., Nakanishi, M., and Hashimoto, A. (1994), Polynomial-time algorithms for computing characteristic strings, in CPM'94, pp. 274-288.

Digital Library

Google Scholar

[13]

Hillis, E. M., Moritz, C., and Mable, B. K. (1996), "Molecular Systematics," 2nd ed., Sinauer Associates Inc., Sunderland.

Google Scholar

[14]

Jiang, T., Trendall, C., Wang, S., Wareham, T., and Zhang, X. (1998) Drug target identification using Gibbs sampling techniques, submitted for publication.

Google Scholar

[15]

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.

Google Scholar

[16]

Longfellow, C. E., Kierzek, It., and Ttu#er, D. H.(1990), Thermodynamic and Spectroscopic Study of Bulge Loops in Oligoribonucleotides, Biochemi# 29, 278-285.

Google Scholar

[17]

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.

Google Scholar

[18]

Macario, A., and Macazio, E. (1990), #Gene Probes for Bacteria," Academic Press, San Diego.

Google Scholar

[19]

Mathews, C. K., and van Holde, K.E. (1990), #Biochemistry," Benjamin/Cummings Publishing Company, Inc., Redwood City.

Google Scholar

[20]

Motwani, R., Naor, J., and Raghavan, P., (1995), Randomized Approximation Algorithms in Combinatorial Optimization Approzimation Algorithms for NP-Hard Problems (D. S. Hochbaum, Ed.), pp. 447-481, PWS Publishing Company, Boston.

Digital Library

Google Scholar

[21]

Motwani, R., and Raghavan, P. (1995), #Randomized Algorithms," Cambridge University Press, Cambridge.

Digital Library

Google Scholar

[22]

Papadimitriou, C. H., and Yannakakis, M. (1991), Optimization, approximation and complexity classes, JCSS 43, 425-440.

Google Scholar

[23]

Proutski, V., and Holme, E. C. (1996), Primer Master: a new program for the design and analysis of PCR primers, CABIOS 12, 253-255.

Google Scholar

[24]

Turner, D. H., Sugimoto, N., and Freier, S. M. (1988), RNA Structure Prediction, Ann. Rev. Biophys. Chem. 17, 167-192.

Google Scholar

[25]

Wetmur, J. G. (1991), DNA Probes: Applications of the Principles of Nucleic Acid Hybridization, Critical Rev. in Biochem. and Mol. Bio. 26, 227-259.

Google Scholar

Cited By

View all

Zohora FRahman M(2016)An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applicationsTheoretical Computer Science10.1016/j.tcs.2016.03.006656:PB(188-214)Online publication date: 20-Dec-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.03.006
Zohora FRahman M(2015)Application of consensus string matching in the diagnosis of allelic heterogeneity involving transposition mutationInternational Journal of Data Mining and Bioinformatics10.1504/IJDMB.2015.07275613:4(360-377)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1504/IJDMB.2015.072756
Della Croce FGarraffa M(2014)The Selective Fixing Algorithm for the closest string problemComputers and Operations Research10.1016/j.cor.2013.07.01741(24-30)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.cor.2013.07.017
Show More Cited By

Index Terms

Distinguishing string selection problems

Recommendations

Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
FAW '09: Proceedings of the 3d International Workshop on Frontiers in Algorithmics

In the paper, we study three related problems, the closest string problem, the farthest string problem and the distinguishing string selection problem. These problems have applications in motif detection, binding sites locating, genetic drug target ...
Distinguishing string selection problems

This paper presents a collection of string algorithms that are at the core of several biological problems such as discovering potential drug targets, creating diagnostic probes, universal primers or unbiased consensus sequences. All these problems ...
A PTAS for Distinguishing (Sub)string Selection
ICALP '02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming

Consider two sets of strings, B (bad genes) and G (good genes), as well as two integers d _b and d _g ( d _b d _g ). A frequently occurring problem in computational biology (andother fields) is to finda (distinguishing) substring s of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

January 1999

992 pages

ISBN:0898714346

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1999

Check for updates

Qualifiers

Article

Conference

SODA99

Sponsor:

SIGACT
SIAM

SODA99: 1999 10th Conference on Discrete Algorithms

January 17 - 19, 1999

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
108
Total Downloads

Downloads (Last 12 months)51
Downloads (Last 6 weeks)8

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zohora FRahman M(2016)An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applicationsTheoretical Computer Science10.1016/j.tcs.2016.03.006656:PB(188-214)Online publication date: 20-Dec-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.03.006
Zohora FRahman M(2015)Application of consensus string matching in the diagnosis of allelic heterogeneity involving transposition mutationInternational Journal of Data Mining and Bioinformatics10.1504/IJDMB.2015.07275613:4(360-377)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1504/IJDMB.2015.072756
Della Croce FGarraffa M(2014)The Selective Fixing Algorithm for the closest string problemComputers and Operations Research10.1016/j.cor.2013.07.01741(24-30)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.cor.2013.07.017
Kociumaka TPachocki JRadoszewski JRytter WWaleń T(2014)On the String Consensus Problem and the Manhattan Sequence Consensus ProblemProceedings of the 21st International Symposium on String Processing and Information Retrieval - Volume 879910.1007/978-3-319-11918-2_24(244-255)Online publication date: 20-Oct-2014
https://dl.acm.org/doi/10.1007/978-3-319-11918-2_24
Mousavi SNasr Esfahani N(2012)A GRASP algorithm for the Closest String Problem using a probability-based heuristicComputers and Operations Research10.1016/j.cor.2011.02.02539:2(238-248)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.cor.2011.02.025
Mousavi SBabaie MMontazerian M(2012)An improved heuristic for the far from most strings problemJournal of Heuristics10.1007/s10732-011-9177-z18:2(239-262)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1007/s10732-011-9177-z
Amir AParyenty HRoditty L(2011)Approximations and partial solutions for the consensus sequence problemProceedings of the 18th international conference on String processing and information retrieval10.5555/2051073.2051090(168-173)Online publication date: 17-Oct-2011
https://dl.acm.org/doi/10.5555/2051073.2051090
Chen ZMa BWang L(2010)A three-string approach to the closest string problemProceedings of the 16th annual international conference on Computing and combinatorics10.5555/1886811.1886868(449-458)Online publication date: 19-Jul-2010
https://dl.acm.org/doi/10.5555/1886811.1886868
Lee TNa JPark HPark KSim J(2010)Finding optimal alignment and consensus of circular stringsProceedings of the 21st annual conference on Combinatorial pattern matching10.5555/1875737.1875765(310-322)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.5555/1875737.1875765
Fu BKao MWang L(2009)Discovering Almost Any Hidden Motif from Multiple Sequences in Polynomial Time with Low Sample Complexity and High Success ProbabilityProceedings of the 6th Annual Conference on Theory and Applications of Models of Computation10.1007/978-3-642-02017-9_26(231-240)Online publication date: 12-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-02017-9_26
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

Efficient Algorithms for the Closest String and Distinguishing String Selection Problems

Distinguishing string selection problems

A PTAS for Distinguishing (Sub)string Selection