Abstract
Let S be a finite set of strings and let T be a subset of S. A characteristic string of T under S is a string that is a common substring of T and that is not a substring of any string in S-T. We present a lineartime algorithm for deciding whether or not there exists a characteristic string of T under S. If such a string exists, then the algorithm returns all the shortest characteristic strings of T under S in that time.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Hasidume, M. Ito, M. Nakanishi and A. Hashimoto: “A linear-time algorithm for computing a shortest characteristic substring of strings” (in Japanese), IEICE Technical Report, COMP93-36, pp.39–46 (July 1993).
D.G. Higgins and P.M. Sharp: “Fast and sensitive multiple sequence alignments on a microcomputer”, CABIOS, 5, 2, pp.151–153 (Apr. 1989).
M.Ito, K. Shimizu, M. Nakanishi and A. Hashimoto: “Polynomial-time algorithms for computing characteristic strings,” Proc. of 5th Symposium on Combinatorial Pattern Matching, To apprear (June 1994).
G.M. Landau and U.Vishkin: “Introducing efficient parallelism into approximate string matching and a new serial algorithm,” Proc. 18th ACM Symp. on Theory of Computing, pp.220–230 (May 1986).
V.I. Levenshtein: “Binary codes capable of correcting deletions, insertions, and reversals”, Cybernetics and Control Theory, 10, 8, pp.707–710(1966)
A.J.L. Macario and E.C. de Macario: “Gene Probes for Bacteria,” Academic Press (1990)
E.M. McCreight: “A space-economical suffix tree construction algorithm”, Journal of ACM, 23, 2, pp.262–272 (Apr. 1976).
M. Nasu, K. Shimada, S. Inaoka, K. Tani and M. Kondo: “ Natural bacterial populations in river water determined by 16S and 23S rRNA-targeted oligonucleotide probes,” (submitted to Biomedical and Environmental Sciences).
W.R. Pearson and D.J. Lipman: “Improved tools for biological sequence comparison”, Proc. Natl. Acad. Sci. USA, 85, pp.2444–2448 (Apr. 1988).
P. Weiner: “Linear pattern matching algorithms,” Proc. IEEE 14th Symposium on Switching and Automata Theory, pp.1–11 (1973)
“Genome Databases,” Science, 254 (Oct. 1991).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nakanishi, M., Hasidume, M., Ito, M., Hashimoto, A. (1994). A linear-time algorithm for computing characteristic strings. In: Du, DZ., Zhang, XS. (eds) Algorithms and Computation. ISAAC 1994. Lecture Notes in Computer Science, vol 834. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58325-4_195
Download citation
DOI: https://doi.org/10.1007/3-540-58325-4_195
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58325-7
Online ISBN: 978-3-540-48653-4
eBook Packages: Springer Book Archive