{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T07:45:06Z","timestamp":1648885506756},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,12,22]],"date-time":"2007-12-22T00:00:00Z","timestamp":1198281600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s10878-007-9132-y","type":"journal-article","created":{"date-parts":[[2007,12,21]],"date-time":"2007-12-21T15:37:23Z","timestamp":1198251443000},"page":"263-278","source":"Crossref","is-referenced-by-count":3,"title":["Alignments with non-overlapping moves, inversions and tandem duplications in O(n 4) time"],"prefix":"10.1007","volume":"16","author":[{"given":"Christian","family":"Ledergerber","sequence":"first","affiliation":[]},{"given":"Christophe","family":"Dessimoz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,12,22]]},"reference":[{"issue":"1","key":"9132_CR1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A Aggarwal","year":"1987","unstructured":"Aggarwal A, Klawe MM, Moran S, Shor P, Wilber R (1987) Geometric applications of a matrix-searching algorithm. Algorithmica 2(1):195\u2013208","journal-title":"Algorithmica"},{"key":"9132_CR2","series-title":"Electronic Notes in Discrete Mathematics","first-page":"365","volume-title":"Proceedings of GRACO 2005","author":"CER Alves","year":"2005","unstructured":"Alves CER, do Lago AP, Vellozo AF (2005) Alignment with non-overlapping inversions in o(n 3log\u2009n) time. In: Proceedings of GRACO 2005. Electronic Notes in Discrete Mathematics, vol\u00a019. Elsevier, Amsterdam, pp\u00a0365\u2013371"},{"issue":"23","key":"9132_CR3","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1006\/jsbi.2001.4392","volume":"134","author":"MA Andrade","year":"2001","unstructured":"Andrade MA, Perez-Iratxeta C, Ponting CP (2001) Protein repeats: structures, functions, and evolution. J\u00a0Struct Biol 134(23):117\u2013131","journal-title":"J\u00a0Struct Biol"},{"issue":"2","key":"9132_CR4","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1006\/jmbi.2001.4776","volume":"310","author":"G Apic","year":"2001","unstructured":"Apic G, Gough J, Teichmann SA (2001) Domain combinations in archaeal, eubacterial and eukaryotic proteomes. J Mol Biol 310(2):311\u2013325","journal-title":"J Mol Biol"},{"issue":"4","key":"9132_CR5","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1006\/jmbi.2001.5288","volume":"315","author":"M Bashton","year":"2002","unstructured":"Bashton M, Chothia C (2002) The geometry of domain combination in proteinsm. J Mol Biol 315(4):927\u2013939","journal-title":"J Mol Biol"},{"issue":"3","key":"9132_CR6","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/j.tcs.2004.02.040","volume":"325","author":"ZZ Chen","year":"2004","unstructured":"Chen ZZ, Gao Y, Lin G, Niewiadomski R, Wang Y, Wu J (2004) A space-efficient algorithm for sequence alignment with inversions and reversals. Theor Comput Sci 325(3):361\u2013372","journal-title":"Theor Comput Sci"},{"issue":"2","key":"9132_CR7","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/1103963.1103971","volume":"1","author":"M Chrobak","year":"2005","unstructured":"Chrobak M, Kolman P, Sgall J (2005) The greedy algorithm for the minimum common string partition problem. ACM Trans Algorithms 1(2):350\u2013366","journal-title":"ACM Trans Algorithms"},{"key":"9132_CR8","unstructured":"Cormode G, Muthukrishnan S (2002) The string edit distance matching problem with moves. In: SODA\u00a0\u201902: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, pp\u00a0667\u2013676"},{"issue":"1","key":"9132_CR9","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1051\/ita:2005011","volume":"39","author":"AP do Lago","year":"2005","unstructured":"do Lago AP, Muchnik I (2005) A sparse dynamic programming algorithm for alignment with non-overlapping inversions. Theor Inform Appl 39(1):175\u2013189","journal-title":"Theor Inform Appl"},{"issue":"2","key":"9132_CR10","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1002\/prot.10156","volume":"48","author":"A Fliess","year":"2002","unstructured":"Fliess A, Motro B, Unger R (2002) Swaps in protein sequences. Proteins 48(2):377\u2013387","journal-title":"Proteins"},{"issue":"2","key":"9132_CR11","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1093\/bioinformatics\/16.2.101","volume":"16","author":"GH Gonnet","year":"2000","unstructured":"Gonnet GH, Hallett MT, Korostensky C, Bernardin L (2000) Darwin v2.0: an interpreted computer language for the biosciences. Bioinformatics 16(2):101\u2013103","journal-title":"Bioinformatics"},{"key":"9132_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences: computer science and computational biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D (1997\/1999) Algorithms on strings, trees, and sequences: computer science and computational biology. Press Syndicate of the University of Cambridge, Cambridge"},{"issue":"11","key":"9132_CR13","doi-asserted-by":"crossref","first-page":"1642","DOI":"10.1101\/gr.520702","volume":"12","author":"H Kaessmann","year":"2002","unstructured":"Kaessmann H, Z\u00f6llner S, Nekrutenko A, Li WH (2002) Signatures of domain shuffling in the human genome. Genome Res 12(11):1642\u20131650","journal-title":"Genome Res"},{"issue":"2","key":"9132_CR14","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1006\/jagm.2001.1191","volume":"41","author":"GM Landau","year":"2001","unstructured":"Landau GM, Ziv-Ukelson M (2001) On the common substring alignment problem. J Algorithms 41(2):339\u2013354","journal-title":"J Algorithms"},{"issue":"1","key":"9132_CR15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1748-7188-1-2","volume":"1","author":"X Liu","year":"2006","unstructured":"Liu X, Wang L (2006) Finding the region of pseudo-periodic tandem repeats in biological sequences. Algorithms Mol Biol 1(1):2","journal-title":"Algorithms Mol Biol"},{"issue":"1","key":"9132_CR16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1093\/nar\/gki152","volume":"33","author":"M Liu","year":"2005","unstructured":"Liu M, Walch H, Wu S, Grigoriev A (2005) Significant expansion of exon-bordering protein domains during animal proteome evolution. Nucleic Acids Res 33(1):95\u2013105","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"9132_CR17","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0304-3975(96)00268-X","volume":"181","author":"D Lopresti","year":"1997","unstructured":"Lopresti D, Tomkins A (1997) Block edit models for approximate string matching. Theor Comput Sci 181(1):159\u2013179","journal-title":"Theor Comput Sci"},{"issue":"2","key":"9132_CR18","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(90)90109-B","volume":"35","author":"M Maes","year":"1990","unstructured":"Maes M (1990) On a cyclic string-to-string correction problem. Inf Process Lett 35(2):73\u201378","journal-title":"Inf Process Lett"},{"issue":"1","key":"9132_CR19","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1006\/jmbi.1999.3136","volume":"293","author":"EM Marcotte","year":"1999","unstructured":"Marcotte EM, Pellegrini M, Yeates TO, Eisenberg D (1999) A census of protein repeats. J Mol Biol 293(1):151\u2013160","journal-title":"J Mol Biol"},{"key":"9132_CR20","unstructured":"Monge G (1781) D\u00e9blai et remblai. M\u00e9moires de l\u2019Acad\u00e9mie Royale des Sciences"},{"key":"9132_CR21","unstructured":"Myers EW (1991) An overview of sequence comparison algorithms in molecular biology. Technical report 91-29, Univ of Arizona, Dept of Computer Science"},{"issue":"3","key":"9132_CR22","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 48(3):443\u2013453","journal-title":"J Mol Biol"},{"issue":"4","key":"9132_CR23","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1137\/S0097539795288489","volume":"27","author":"JP Schmidt","year":"1998","unstructured":"Schmidt JP (1998) All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM J Comput 27(4):972\u2013992","journal-title":"SIAM J Comput"},{"issue":"4","key":"9132_CR24","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/BF02459633","volume":"54","author":"M Schoeninger","year":"1992","unstructured":"Schoeninger M, Waterman MS (1992) A local algorithm for dna sequence alignment with inversions. Bull Math Biol 54(4):521\u2013536","journal-title":"Bull Math Biol"},{"issue":"20","key":"9132_CR25","doi-asserted-by":"crossref","first-page":"5053","DOI":"10.1242\/dev.01382","volume":"131","author":"T Shandala","year":"2004","unstructured":"Shandala T, Gregory SL, Dalton HE, Smallhorn M, Saint R (2004) Citron kinase is an essential effector of the pbl-activated rho signalling pathway in drosophila melanogaster. Development 131(20):5053\u20135063","journal-title":"Development"},{"key":"9132_CR26","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/3-540-45452-7_9","volume-title":"CPM \u201902: Proceedings of the 13th annual symposium on combinatorial pattern matching","author":"D Shapira","year":"2002","unstructured":"Shapira D, Storer JA (2002) Edit distance with move operations. In: CPM \u201902: Proceedings of the 13th annual symposium on combinatorial pattern matching, London, UK. Springer, Berlin, pp\u00a085\u201398"},{"key":"9132_CR27","series-title":"LNCS","volume-title":"WABI","author":"AF Vellozo","year":"2006","unstructured":"Vellozo AF, Alves CER, do Lago AP (2006) Alignment with non-overlapping inversions in o(n 3)-time. In: WABI, LNCS, vol\u00a04175. Springer, Berlin"},{"issue":"3","key":"9132_CR28","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/s00239-004-0318-y","volume":"61","author":"MD Vibranovski","year":"2005","unstructured":"Vibranovski MD, Sakabe NJ, de Oliveira RS, de Souza SJ (2005) Signs of ancient and modern exon-shuffling are correlated to the distribution of ancient and modern domains along proteins. J Mol Evol 61(3):341\u2013350","journal-title":"J Mol Evol"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9132-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9132-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9132-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:12Z","timestamp":1559276292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9132-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,22]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9132"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9132-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,22]]}}}