{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T19:34:11Z","timestamp":1791228851237,"version":"4.1.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1996,8,1]],"date-time":"1996-08-01T00:00:00Z","timestamp":838857600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1996,8]]},"DOI":"10.1007\/bf01192694","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T10:55:34Z","timestamp":1108724134000},"page":"387-405","source":"Crossref","is-referenced-by-count":12,"title":["DNA sequencing and string learning"],"prefix":"10.1007","volume":"29","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"4","key":"BF01192694_CR1","first-page":"343","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin and P. D. Laird. Learning from noisy examples.Machine Learning 2(4), 343\u2013370, 1988.","journal-title":"Machine Learning"},{"key":"BF01192694_CR2","doi-asserted-by":"crossref","unstructured":"A. Blum, T. Jiang, M. Li, J. Tromp, and M. Yannakakis, Linear approximation of shortest superstrings. To appear inJournal of the ACM; also presented at 23rd ACM Symp. on Theory of Computing, New Orleans, 1991.","DOI":"10.1145\/103418.103455"},{"key":"BF01192694_CR3","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"24","author":"A. Blumer","year":"1987","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Occam's razor.Information Processing Letters 24, 377\u2013380, 1987.","journal-title":"Information Processing Letters"},{"key":"BF01192694_CR4","doi-asserted-by":"crossref","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and Vapnik-Chervonenkis dimension.Journal of the ACM 35(4), 1989.","DOI":"10.1145\/76359.76371"},{"key":"BF01192694_CR5","doi-asserted-by":"crossref","unstructured":"V. Chv\u00e1tal. A greedy heuristic for the set covering problem.Mathematics of Operations Research 4(3), 1979.","DOI":"10.1287\/moor.4.3.233"},{"issue":"1","key":"BF01192694_CR6","first-page":"59","volume":"1","author":"R. Drmanac","year":"1992","unstructured":"R. Drmanac and C. Crkvenjakov. Sequencing by hybridization (SBH) with oligonucleotide probes as an integral approach for the analysis of complex genomes.International Journal of Genomic Research 1(1), 59\u201379, 1992.","journal-title":"International Journal of Genomic Research"},{"key":"BF01192694_CR7","unstructured":"D. Freifelder.Molecular Biology. Jones & Bartlett, 1983."},{"issue":"11","key":"BF01192694_CR8","doi-asserted-by":"crossref","first-page":"1164","DOI":"10.1145\/4547.4550","volume":"28","author":"P. Freidland","year":"1985","unstructured":"P. Freidland and L. Kedes. Discovering the secrets of DNA.Communications of the ACM 28(11), 1164\u20131186, 1985.","journal-title":"Communications of the ACM"},{"key":"BF01192694_CR9","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J. Gallant","year":"1980","unstructured":"J. Gallant, D. Maier, and J. Storer. On finding minimal length superstring.Journal of Computer and System Sciences 20, 50\u201358, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01192694_CR10","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson.Computers and Intractability. Freeman, New York, 1979."},{"issue":"2","key":"BF01192694_CR11","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0004-3702(88)90002-1","volume":"36","author":"D. Haussler","year":"1988","unstructured":"D. Haussler. Quantifying inductive bias: AI learning algorithms and Valiant's model.Artificial Intelligence 36(2), 177\u2013221, 1988.","journal-title":"Artificial Intelligence"},{"key":"BF01192694_CR12","doi-asserted-by":"crossref","unstructured":"D. Helmbold, R. Sloan, and M. Warmuth. Learning nested differences of intersection-closed classes.Proc. 2nd Workshop on Computational Learning Theory, pp. 41\u201356, 1989.","DOI":"10.1016\/B978-0-08-094829-4.50006-4"},{"key":"BF01192694_CR13","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0304-3975(93)90167-R","volume":"119","author":"T. Jiang","year":"1993","unstructured":"T. Jiang and M. Li. On the complexity of learning strings and sequences.Theoretical Computer Science 119, 363\u2013371, 1993.","journal-title":"Theoretical Computer Science"},{"key":"BF01192694_CR14","unstructured":"T. Jiang and M. Li. Approximating shortest superstrings with constraints. To appear inTheoretical Computer Science."},{"key":"BF01192694_CR15","doi-asserted-by":"crossref","unstructured":"R. Karp, Mapping the genome: some combinatorial problems arising in molecular biology.Proc. 23rdACM Symp. on Theory of Computing, pp. 278\u2013285, 1993.","DOI":"10.1145\/167088.167170"},{"key":"BF01192694_CR16","unstructured":"M. Kearns. The computational complexity of machine learning. Ph.D. Thesis, Report TR-13-89, Harvard University, 1989."},{"issue":"4","key":"BF01192694_CR17","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1137\/0222052","volume":"22","author":"M. Kearns","year":"1993","unstructured":"M. Kearns and M. Li. Learning in the presence of malicious errors.SIAM Journal on Computing 22(4), 807\u2013837, 1993.","journal-title":"SIAM Journal on Computing"},{"key":"BF01192694_CR18","doi-asserted-by":"crossref","unstructured":"M. Kearns, M. Li, L. Pitt, and L. G. Valiant. On the learnability of Boolean formulae.Proc. 19thACM Symp. on Theory of Computing, pp. 285\u2013295, 1987.","DOI":"10.1145\/28395.28426"},{"key":"BF01192694_CR19","doi-asserted-by":"crossref","unstructured":"G. Landau and U. Vishkin. Efficient string matching in the presence of errors.Proc. 26thIEEE Symp. on Foundations of Computer Science, pp. 126\u2013136, 1985.","DOI":"10.1109\/SFCS.1985.22"},{"key":"BF01192694_CR20","volume-title":"Computational Molecular Biology, Sources and Methods for Sequence Analysis","year":"1988","unstructured":"A. Lesk (editor).Computational Molecular Biology, Sources and Methods for Sequence Analysis. Oxford University Press, Oxford, 1988."},{"key":"BF01192694_CR21","doi-asserted-by":"crossref","unstructured":"M. Li. Towards a DNA sequencing theory.Proc. 31stIEEE Symp. on Foundations of Computer Science, pp. 125\u2013134, 1990.","DOI":"10.1109\/FSCS.1990.89531"},{"key":"BF01192694_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3860-5","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"1993","unstructured":"M. Li and P. Vit\u00e1nyi.An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, New York, 1993."},{"key":"BF01192694_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-12405-5","volume-title":"Machine Learning","author":"R. Michalski","year":"1983","unstructured":"R. Michalski, J. Carbonell, and T. Mitchell.Machine Learning. Morgan Kaufmann, Los Altos, CA, 1983."},{"key":"BF01192694_CR24","unstructured":"H. Peltola, H. Soderlund, J. Tarhio, and E. Ukkonen. Algorithms for some string matching problems arising in molecular genetics.Information Processing 83 (Proc.IFIP Congress, 1983), pp. 53\u201364."},{"issue":"3","key":"BF01192694_CR25","first-page":"229","volume":"2","author":"R. Rivest","year":"1987","unstructured":"R. Rivest, Learning decision-lists.Machine Learning 2(3), 229\u2013246, 1987.","journal-title":"Machine Learning"},{"key":"BF01192694_CR26","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1126\/science.8211178","volume":"262","author":"L. Smith","year":"1993","unstructured":"L. Smith, The future of DNA sequencing.Science 262, 530\u2013532, 1993.","journal-title":"Science"},{"issue":"15","key":"BF01192694_CR27","doi-asserted-by":"crossref","first-page":"4731","DOI":"10.1093\/nar\/10.15.4731","volume":"10","author":"R. Staden","year":"1982","unstructured":"R. Staden, Automation of the computer handling of gel reading data produced by the shotgun method of DNA sequencing.Nucleic Acids Research 10(15), 4731\u20134751, 1982.","journal-title":"Nucleic Acids Research"},{"key":"BF01192694_CR28","volume-title":"Data Compression: Methods and Theory","author":"J. Storer","year":"1988","unstructured":"J. Storer,Data Compression: Methods and Theory. Computer Science Press, Rockville, MD, 1988."},{"key":"BF01192694_CR29","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J. Tarhio","year":"1988","unstructured":"J. Tarhio and E. Ukkonen. A greedy approximation algorithm for constructing shortest common super-strings.Theoretical Computer Science 57, 131\u2013145, 1988.","journal-title":"Theoretical Computer Science"},{"key":"BF01192694_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","volume":"83","author":"J. Turner","year":"1989","unstructured":"J. Turner, Approximation algorithms for the shortest common superstring problem.Information and Computation 83, 1\u201320, 1989.","journal-title":"Information and Computation"},{"issue":"11","key":"BF01192694_CR31","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant, A theory of the learnable.Communications of the ACM 27(11), 1134\u20131142, 1984.","journal-title":"Communications of the ACM"},{"key":"BF01192694_CR32","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1098\/rsta.1984.0069","volume":"312","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant. Deductive learning.Philosophical Transactions of the Royal Society of London. Series A 312, 441\u2013446, 1984.","journal-title":"Philosophical Transactions of the Royal Society of London. Series A"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01192694.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01192694\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01192694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:03:50Z","timestamp":1734955430000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01192694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,8]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,8]]}},"alternative-id":["BF01192694"],"URL":"https:\/\/doi.org\/10.1007\/bf01192694","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,8]]}}}