{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:38Z","timestamp":1725489158843},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73545-8_17","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T09:44:11Z","timestamp":1187343851000},"page":"151-164","source":"Crossref","is-referenced-by-count":0,"title":["Alignments with Non-overlapping Moves, Inversions and Tandem Duplications in O(n 4) Time"],"prefix":"10.1007","author":[{"given":"Christian","family":"Ledergerber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christophe","family":"Dessimoz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"17_CR1","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":"2","key":"17_CR2","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1002\/prot.10156","volume":"48","author":"A. Fliess","year":"2002","unstructured":"Fliess, A., Motro, B., Unger, R.: Swaps in protein sequences. Proteins.\u00a048(2), 377\u2013387 (2002)","journal-title":"Proteins."},{"issue":"1","key":"17_CR3","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0304-3975(96)00268-X","volume":"181","author":"D. Lopresti","year":"1997","unstructured":"Lopresti, D., Tomkins, A.: Block edit models for approximate string matching. Theor. Comput. Sci.\u00a0181(1), 159\u2013179 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-45452-7_9","volume-title":"Combinatorial Pattern Matching","author":"D. Shapira","year":"2002","unstructured":"Shapira, D., Storer, J.A.: Edit distance with move operations. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol.\u00a02373, pp. 85\u201398. Springer, Heidelberg (2002)"},{"issue":"2","key":"17_CR5","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/1103963.1103971","volume":"1","author":"M. Chrobak","year":"2005","unstructured":"Chrobak, M., Kolman, P., Sgall, J.: The greedy algorithm for the minimum common string partition problem. ACM Trans. Algorithms\u00a01(2), 350\u2013366 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"17_CR6","series-title":"Society for Industrial and Applied Mathematics","first-page":"667","volume-title":"SODA 2002","author":"G. Cormode","year":"2002","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: SODA 2002. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA. Society for Industrial and Applied Mathematics, pp. 667\u2013676. ACM Press, New York (2002)"},{"key":"17_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/267521.267531","volume-title":"RECOMB 1997","author":"A. Caprara","year":"1997","unstructured":"Caprara, A.: Sorting by reversals is difficult. In: RECOMB 1997. Proceedings of the first annual international conference on Computational molecular biology, pp. 75\u201383. ACM Press, New York (1997)"},{"issue":"4","key":"17_CR8","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/BF02459633","volume":"54","author":"M. Schoeninger","year":"1992","unstructured":"Schoeninger, M., Waterman, M.S.: A local algorithm for dna sequence alignment with inversions. Bull. Math. Biol.\u00a054(4), 521\u2013536 (1992)","journal-title":"Bull. Math. Biol."},{"issue":"3","key":"17_CR9","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/j.tcs.2004.02.040","volume":"325","author":"Z.Z. Chen","year":"2004","unstructured":"Chen, Z.Z., Gao, Y., Lin, G., Niewiadomski, R., Wang, Y., Wu, J.: A space-efficient algorithm for sequence alignment with inversions and reversals. Theor. Comput. Sci.\u00a0325(3), 361\u2013372 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"17_CR10","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1051\/ita:2005011","volume":"39","author":"A.P. Lago do","year":"2005","unstructured":"do Lago, A.P., Muchnik, I.: A sparse dynamic programming algorithm for alignment with non-overlapping inversions. Theoret. Informatics Appl.\u00a039(1), 175\u2013189 (2005)","journal-title":"Theoret. Informatics Appl."},{"key":"17_CR11","series-title":"Electronic Notes in Discrete Mathematics","first-page":"365","volume-title":"Proceedings of GRACO 2005","author":"C.E.R. Alves","year":"2005","unstructured":"Alves, C.E.R., do Lago, A.P., Vellozo, A.F.: Alignment with non-overlapping inversions in o(n\n                3 logn) time. In: Proceedings of GRACO 2005. Electronic Notes in Discrete Mathematics, vol.\u00a019, pp. 365\u2013371. Elsevier, Amsterdam (2005)"},{"key":"17_CR12","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/11851561_18","volume-title":"Algorithms in Bioinformatics","author":"A.F. Vellozo","year":"2006","unstructured":"Vellozo, A.F., Alves, C.E.R., do Lago, A.P.: Alignment with non-overlapping inversions in o(n\n                3)-time. In: B\u00fccher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS (LNBI), vol.\u00a04175, pp. 186\u2013196. Springer, Heidelberg (2006)"},{"issue":"2","key":"17_CR13","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1006\/jmbi.2001.4776","volume":"310","author":"G. Apic","year":"2001","unstructured":"Apic, G., Gough, J., Teichmann, S.A.: Domain combinations in archaeal, eubacterial and eukaryotic proteomes. J. Mol. Biol.\u00a0310(2), 311\u2013325 (2001)","journal-title":"J. Mol. Biol."},{"issue":"11","key":"17_CR14","doi-asserted-by":"publisher","first-page":"1642","DOI":"10.1101\/gr.520702","volume":"12","author":"H. Kaessmann","year":"2002","unstructured":"Kaessmann, H., Z\u00f6llner, S., Nekrutenko, A., Li, W.H.: Signatures of domain shuffling in the human genome. Genome Res.\u00a012(11), 1642\u20131650 (2002)","journal-title":"Genome Res."},{"issue":"1","key":"17_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1093\/nar\/gki152","volume":"33","author":"M. Liu","year":"2005","unstructured":"Liu, M., Walch, H., Wu, S., Grigoriev, A.: Significant expansion of exon-bordering protein domains during animal proteome evolution. Nucleic Acids Res.\u00a033(1), 95\u2013105 (2005)","journal-title":"Nucleic Acids Res."},{"issue":"3","key":"17_CR16","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s00239-004-0318-y","volume":"61","author":"M.D. Vibranovski","year":"2005","unstructured":"Vibranovski, M.D., Sakabe, N.J., de Oliveira, R.S., de Souza, S.J.: Signs of ancient and modern exon-shuffling are correlated to the distribution of ancient and modern domains along proteins. J. Mol. Evol.\u00a061(3), 341\u2013350 (2005)","journal-title":"J. Mol. Evol."},{"issue":"4","key":"17_CR17","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1006\/jmbi.2001.5288","volume":"315","author":"M. Bashton","year":"2002","unstructured":"Bashton, M., Chothia, C.: The geometry of domain combination in proteins. J. Mol. Biol.\u00a0315(4), 927\u2013939 (2002)","journal-title":"J. Mol. Biol."},{"issue":"20","key":"17_CR18","doi-asserted-by":"publisher","first-page":"5053","DOI":"10.1242\/dev.01382","volume":"131","author":"T. Shandala","year":"2004","unstructured":"Shandala, T., Gregory, S.L., Dalton, H.E., Smallhorn, M., Saint, R.: Citron kinase is an essential effector of the pbl-activated rho signalling pathway in drosophila melanogaster. Development\u00a0131(20), 5053\u20135063 (2004)","journal-title":"Development"},{"issue":"2-3","key":"17_CR19","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1006\/jsbi.2001.4392","volume":"134","author":"M.A. Andrade","year":"2001","unstructured":"Andrade, M.A., Perez-Iratxeta, C., Ponting, C.P.: Protein repeats: structures, functions, and evolution. J. Struct. Biol.\u00a0134(2-3), 117\u2013131 (2001)","journal-title":"J. Struct. Biol."},{"issue":"1","key":"17_CR20","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1006\/jmbi.1999.3136","volume":"293","author":"E.M. Marcotte","year":"1999","unstructured":"Marcotte, E.M., Pellegrini, M., Yeates, T.O., Eisenberg, D.: A census of protein repeats. J. Mol. Biol.\u00a0293(1), 151\u2013160 (1999)","journal-title":"J. Mol. Biol."},{"issue":"2","key":"17_CR21","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0020-0190(90)90109-B","volume":"35","author":"M. Maes","year":"1990","unstructured":"Maes, M.: On a cyclic string-to-string correction problem. Inf. Process. Lett.\u00a035(2), 73\u201378 (1990)","journal-title":"Inf. Process. Lett."},{"key":"17_CR22","unstructured":"Myers, E.W.: An overview of sequence comparison algorithms in molecular biology. Technical Report 91-29, Univ. of Arizona, Dept. of Computer Science (1991)"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: computer science and computational biology. Press Syndicate of the University of Cambridge, Cambridge (1997\/1999)","DOI":"10.1017\/CBO9780511574931"},{"issue":"2","key":"17_CR24","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1006\/jagm.2001.1191","volume":"41","author":"G.M. Landau","year":"2001","unstructured":"Landau, G.M., Ziv-Ukelson, M.: On the common substring alignment problem. J. Algorithms\u00a041(2), 338\u2013354 (2001)","journal-title":"J. Algorithms"},{"issue":"4","key":"17_CR25","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/S0097539795288489","volume":"27","author":"J.P. Schmidt","year":"1998","unstructured":"Schmidt, J.P.: All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM J. Comput.\u00a027(4), 972\u2013992 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"17_CR26","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M.M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica\u00a02(1), 195\u2013208 (1987)","journal-title":"Algorithmica"},{"issue":"2","key":"17_CR27","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1093\/bioinformatics\/16.2.101","volume":"16","author":"G.H. Gonnet","year":"2000","unstructured":"Gonnet, G.H., Hallett, M.T., Korostensky, C., Bernardin, L.: Darwin v. 2.0: An interpreted computer language for the biosciences. Bioinformatics\u00a016(2), 101\u2013103 (2000)","journal-title":"Bioinformatics"},{"key":"17_CR28","unstructured":"Monge, G.: D\u00e9blai et remblai. M\u00e9moires de l\u2019Acad\u00e9mie Royale des Sciences (1781)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:17:45Z","timestamp":1619504265000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735441","9783540735458"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}