{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:29:51Z","timestamp":1725560991348},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540206804"},{"type":"electronic","value":"9783540245971"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24597-1_16","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T07:39:20Z","timestamp":1280389160000},"page":"183-194","source":"Crossref","is-referenced-by-count":16,"title":["Comparing Sequences with Segment Rearrangements"],"prefix":"10.1007","author":[{"given":"Funda","family":"Ergun","sequence":"first","affiliation":[]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[]},{"given":"S. Cenk","family":"Sahinalp","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Arslan, A.N., Egecioglu, O., Pevzner, P.A.: A new approach to sequence comparison: normalized sequence alignment. In: Proceedings of RECOMB 2001 (2001)","DOI":"10.1145\/369133.369146"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Bafna, V., Pevzner, P.: Genome Rearrangements and Sorting by Reversals. In: Proc. IEEE FOCS, pp. 148\u2013157(1993)","DOI":"10.1109\/SFCS.1993.366872"},{"key":"16_CR3","unstructured":"Bafna, V., Pevzner, P.: Sorting Permutations by Transpositions. In: Proc. ACM-SIAM SODA, pp. 614\u2013623 (1995)"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Benedetto, D., Caglioti, E., Lorento, V.: Language Trees and Zipping. Physical Review Letters\u00a088(4) (January 2002)","DOI":"10.1103\/PhysRevLett.88.048702"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Ball, P.: Algorithm makes tongue tree, Nature, Science update, January 22 (2002)","DOI":"10.1038\/news020121-2"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Borodin, A., Ostrovsky, R., Rabani, Y.: Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. In: Proc. of ACM STOC (1999)","DOI":"10.1145\/301250.301330"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Rasala, A., Sahai, A., Shelat, A.: Approximating the smallest grammar: Kolmogorov complexity in natural models. In: Proc. ACM STOC 2002, pp. 792\u2013801 (2002)","DOI":"10.1145\/509907.510021"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Caprara, A.: Formulations and complexity of multiple sorting by reversals. In: Proc. ACM RECOMB (1999)","DOI":"10.1145\/299432.299461"},{"key":"16_CR9","unstructured":"Christie, D.: A 3\/2 approximation algorithm for sorting by reversals. In: Proc. ACMSIAM SODA (1998)"},{"key":"16_CR10","unstructured":"Cormode, G., Paterson, M., Sahinalp, S.C., Vishkin, U.: Communication Complexity of Document Exchange. In: Proc. ACM-SIAM Symp. on Discrete Algorithms (2000)"},{"key":"16_CR11","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: Proc. ACM-SIAM Symp. on Discrete Algorithms (2001)"},{"key":"16_CR12","unstructured":"Durand, Nadeau, Salzberg, Sankof (eds.): DIMACS Workshop on Whole Genome Comparison (2001)"},{"key":"16_CR13","unstructured":"Ergun, F., Muthukrishnan, S., Sahinalp, S.C.: Comparing sequences with segment rearrangements, http:\/\/cs.rutgers.edu\/muthu\/resrch_chrono.html"},{"issue":"6","key":"16_CR14","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D. Hirschberg","year":"1975","unstructured":"Hirschberg, D.: A Linear Space Algorithm for Computing Maximal Common Subsequences. CACM\u00a018(6), 341\u2013343 (1975)","journal-title":"CACM"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Hannenhalli, S., Pevzner, P.: Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proc. IEEE FOCS, pp. 581\u2013592 (1995)","DOI":"10.1109\/SFCS.1995.492588"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Hannenhalli, S., Pevzner, P.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. In: Proc. ACM STOC, pp. 178\u2013189 (1995)","DOI":"10.1145\/225058.225112"},{"key":"16_CR17","unstructured":"Andoni, A., Deza, M., Gupta, A., Indyk, P., Raskhodnikova, S.: Lower Bounds for Embedding of Edit Distance into Normed Spaces. In: To appear in 14th Symposium on Discrete Algorithms (SODA) (2003)"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Ji, Y., Eichler, E.E., Schwartz, S., Nicholls, R.D.: Structure of Chromosomal Duplications and their Role in Mediating Human Genomic Disorders. Genome Research\u00a010 (2000)","DOI":"10.1101\/gr.10.5.597"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.: A faster and simpler algorithm for sorting signed permutations by reversals. SIAM Journal on Computing (2000)","DOI":"10.1137\/S0097539798334207"},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R. Karp","year":"1987","unstructured":"Karp, R., Rabin, M.: Efficient randomized pattern-matching algorithms. IBM J. of Res. and Dev.\u00a031, 249\u2013260 (1987)","journal-title":"IBM J. of Res. and Dev."},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. In: Proc. ACM STOC, pp. 614\u2013623 (1998)","DOI":"10.1145\/276698.276877"},{"issue":"8","key":"16_CR22","first-page":"707","volume":"10","author":"V.I. Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions. Insertions and reversals. Cybernetics and Control Theory\u00a010(8), 707\u2013710 (1966)","journal-title":"Cybernetics and Control Theory"},{"key":"16_CR23","first-page":"409","volume":"15","author":"E.S. Lander","year":"2001","unstructured":"Lander, E.S., et al.: Initial sequencing and analysis of the human genome. Nature\u00a015, 409 (2001)","journal-title":"Nature"},{"key":"16_CR24","unstructured":"Lehman, E., Shelat, A.: Approximation algorithms for grammar-based compression. In: Proc. ACM-SIAM SODA 2002, pp. 205\u2013212 (2002)"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"Li, M., Badger, J.H., Xin, C., Kwong, S., Kearney, P., Zhang, H.: An information based sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics\u00a017 (2001)","DOI":"10.1093\/bioinformatics\/17.2.149"},{"key":"16_CR26","unstructured":"Li, M., Chen, X., Li, X., Ma, B., Vitanyi, P.: The Similarity Metric. In: Proceedings of ACM-SIAM SODA, Baltimore MD (2003)"},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"Lopresti, D., Tomkins, A.: Block edit models for approximate string matching. Theoretical Computer Science (1996)","DOI":"10.1016\/S0304-3975(96)00268-X"},{"key":"16_CR28","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and applications (2003), http:\/\/athos.rutgers.edu\/muthu\/stream-1-1.ps"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Sahinalp, S.C.: Approximate nearest neighbors and sequence comparison with block operations. In: Proc. ACM STOC (2000)","DOI":"10.1145\/335305.335353"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Sahinalp, S.C.: Improved algorithm for sequence comparison with block reversals. In: Proc. LATIN (2002)","DOI":"10.1007\/3-540-45995-2_30"},{"issue":"3","key":"16_CR31","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S.B. Needleman","year":"1970","unstructured":"Needleman, S.B., Wunsch, C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol.\u00a048(3), 443\u2013453 (1970)","journal-title":"J. Mol. Biol."},{"issue":"1","key":"16_CR32","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/322234.322237","volume":"28","author":"M. Rodeh","year":"1981","unstructured":"Rodeh, M., Pratt, V., Even, S.: Linear Algorithm for Data Compression via String Matching. JACM\u00a028(1), 16\u201324 (1981)","journal-title":"JACM"},{"key":"16_CR33","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P. Sellers","year":"1980","unstructured":"Sellers, P.: The Theory and Computation of Evolutionary Distances: Pattern Recognition. Journal of Algorithms\u00a01, 359\u2013373 (1980)","journal-title":"Journal of Algorithms"},{"key":"16_CR34","doi-asserted-by":"crossref","unstructured":"Shapira, D., Storer, J.: In-place Differential File Compression. In: Proc. DCC, pp. 263\u2013272 (2003)","DOI":"10.1109\/DCC.2003.1194017"},{"key":"16_CR35","volume-title":"Data compression: methods and theory","author":"J.A. Storer","year":"1988","unstructured":"Storer, J.A.: Data compression: methods and theory. Computer Science Press, Rockville (1988)"},{"issue":"4","key":"16_CR36","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/357401.357404","volume":"2","author":"W.F. Tichy","year":"1984","unstructured":"Tichy, W.F.: The string-to-string correction problem with block moves. ACM Trans. on Computer Systems\u00a02(4), 309\u2013321 (1984)","journal-title":"ACM Trans. on Computer Systems"},{"key":"16_CR37","first-page":"291","volume":"16","author":"C. Venter","year":"2001","unstructured":"Venter, C., et al.: The sequence of the human genome. Science\u00a016, 291 (2001)","journal-title":"Science"},{"issue":"3","key":"16_CR38","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1093\/bioinformatics\/15.3.194","volume":"15","author":"J.S. Varre","year":"1999","unstructured":"Varre, J.S., Delahaye, J.P., Rivals, E.: The Transformation Distance: A Dissimilarity Measure Based on Movements of Segments. Bioinformatics\u00a015(3), 194\u2013202 (1999)","journal-title":"Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24597-1_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T23:43:04Z","timestamp":1559346184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24597-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206804","9783540245971"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24597-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}