{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T23:53:30Z","timestamp":1781654010246,"version":"3.54.5"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["#EP\/M506357\/1"],"award-info":[{"award-number":["#EP\/M506357\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1186\/s13015-016-0076-6","type":"journal-article","created":{"date-parts":[[2016,5,9]],"date-time":"2016-05-09T21:26:15Z","timestamp":1462829175000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Circular sequence comparison: algorithms and applications"],"prefix":"10.1186","volume":"11","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Mercas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nadia","family":"Pisanti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ahmad","family":"Retha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fatima","family":"Vayani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,5,10]]},"reference":[{"issue":"32","key":"76_CR1","doi-asserted-by":"crossref","first-page":"26999","DOI":"10.1074\/jbc.R112.390344","volume":"287","author":"DJ Craik","year":"2012","unstructured":"Craik DJ, Allewell NM. Thematic minireview series on circular proteins. J Biol Chem. 2012;287(32):26999\u20137000.","journal-title":"J Biol Chem"},{"key":"76_CR2","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1146\/annurev.bi.40.070171.004343","volume":"40","author":"DR Helinski","year":"1971","unstructured":"Helinski DR, Clewell DB. Circular DNA. Annu Rev Biochem. 1971;40:899\u2013942.","journal-title":"Annu Rev Biochem"},{"key":"76_CR3","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1128\/AAC.01239-12","volume":"57","author":"CS Castillo Del","year":"2013","unstructured":"Del Castillo CS, Hikima JI, Jang HB, Nho SW, Jung TS, Wongtavatchai J, Kondo H, Hirono I, Takeyama H, Aoki T. Comparative sequence analysis of a multidrug-resistant plasmid from Aeromonas hydrophila. Antimicrob Agents Chemother. 2013;57:120\u20139.","journal-title":"Antimicrob Agents Chemother"},{"issue":"2","key":"76_CR4","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0005-2728(98)00161-3","volume":"1410","author":"JW Taanman","year":"1999","unstructured":"Taanman JW. The mitochondrial genome: structure, transcription, translation and replication. Biochem Biophys Acta Bioenerg. 1999;1410(2):103\u201323.","journal-title":"Biochem Biophys Acta Bioenerg"},{"issue":"3","key":"76_CR5","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1101\/gr.5941007","volume":"17","author":"A Goios","year":"2007","unstructured":"Goios A, Pereira L, Bogue M, Macaulay V, Amorim A. mtDNA phylogeny and evolution of laboratory mouse strains. Genome Res. 2007;17(3):293\u20138.","journal-title":"Genome Res"},{"issue":"9","key":"76_CR6","doi-asserted-by":"crossref","first-page":"e110685","DOI":"10.1371\/journal.pone.0110685","volume":"10","author":"Z Wang","year":"2014","unstructured":"Wang Z, Wu M. Phylogenomic reconstruction indicates mitochondrial ancestor was an energy parasite. PLoS One. 2014;10(9):e110685.","journal-title":"PLoS One"},{"issue":"6","key":"76_CR7","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1111\/j.1365-313X.2007.03394.x","volume":"53","author":"S Cohen","year":"2008","unstructured":"Cohen S, Houben A, Segal D. Extrachromosomal circular DNA derived from tandemly repeated genomic sequences in plants. Plant J. 2008;53(6):1027\u201334.","journal-title":"Plant J"},{"key":"76_CR8","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.semcancer.2006.10.007","volume":"17","author":"F Kuttler","year":"2007","unstructured":"Kuttler F, Mai S. Formation of non-random extrachromosomal elements during development, differentiation and oncogenesis. Semin Cancer Biol. 2007;17:56\u201364.","journal-title":"Semin Cancer Biol"},{"key":"76_CR9","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1186\/1471-2105-5-96","volume":"5","author":"R Brodie","year":"2004","unstructured":"Brodie R, Smith AJ, Roper RL, Tcherepanov V, Upton C. Base-by-base: single nucleotide-level analysis of whole viral genome alignments. BMC Bioinform. 2004;5:96.","journal-title":"BMC Bioinform"},{"issue":"4","key":"76_CR10","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1101\/gr.1960404","volume":"14","author":"N Bray","year":"2004","unstructured":"Bray N, Pachter L. MAVID: constrained ancestral alignment of multiple sequences. Genome Res. 2004;14(4):693\u20139.","journal-title":"Genome Res"},{"key":"76_CR11","first-page":"93","volume":"83","author":"A Mosig","year":"2006","unstructured":"Mosig A, Hofacker IL, Stadler PF. Comparative analysis of cyclic sequences: viroids and other small circular RNAs. GCB. 2006;83:93\u2013102.","journal-title":"GCB"},{"issue":"12","key":"76_CR12","doi-asserted-by":"crossref","first-page":"2438","DOI":"10.1271\/bbb.62.2438","volume":"62","author":"Y Kawai","year":"1998","unstructured":"Kawai Y, Saito T, Kitazawa H, Itoh T. Gassericin A; an uncommon cyclic bacteriocin produced by Lactobacillus gasseri LA39 linked at N-and C-terminal ends. Biosci Biotech Biochem. 1998;62(12):2438\u201340.","journal-title":"Biosci Biotech Biochem"},{"issue":"3","key":"76_CR13","doi-asserted-by":"crossref","first-page":"1589","DOI":"10.1128\/AEM.69.3.1589-1597.2003","volume":"69","author":"R Kemperman","year":"2003","unstructured":"Kemperman R, Kuipers A, Karsens H, Nauta A, Kuipers O, Kok J. Identification and characterization of two novel clostridial bacteriocins, circularin A and closticin 574. Appl Environ Microbiol. 2003;69(3):1589\u201397.","journal-title":"Appl Environ Microbiol"},{"issue":"4","key":"76_CR14","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1093\/molbev\/msj091","volume":"23","author":"J Weiner","year":"2006","unstructured":"Weiner J, Bornberg-Bauer E. Evolution of circular permutations in multidomain proteins. Mol Biol Evol. 2006;23(4):734\u201343.","journal-title":"Mol Biol Evol"},{"issue":"5","key":"76_CR15","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0968-0004(00)89003-9","volume":"20","author":"CP Ponting","year":"1995","unstructured":"Ponting CP, Russell RB. Swaposins: circular permutations within genes encoding saposin homologues. Trends Biochem Sci. 1995;20(5):179\u201380.","journal-title":"Trends Biochem Sci"},{"key":"76_CR16","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1093\/nar\/28.1.15","volume":"28","author":"DA Benson","year":"2000","unstructured":"Benson DA, Karsch-Mizrachi I, Lipman DJ, Ostell J, Rapp BA, Wheeler DL. GenBank. Nucleic Acids Res. 2000;28:15\u20138.","journal-title":"Nucleic Acids Res"},{"issue":"6","key":"76_CR17","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1016\/S0168-9525(00)02024-2","volume":"16","author":"P Rice","year":"2000","unstructured":"Rice P, Longden I, Bleasby A. EMBOSS: the European molecular biology open software suite. Trends Genet. 2000;16(6):276\u20137.","journal-title":"Trends Genet"},{"key":"76_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-9-1","volume":"9","author":"C Barton","year":"2014","unstructured":"Barton C, Iliopoulos CS, Pissis SP. Fast algorithms for approximate circular string matching. Algorithms Mol Biol. 2014;9:1\u201310.","journal-title":"Algorithms Mol Biol"},{"key":"76_CR19","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-319-15579-1_6","volume-title":"Average-case optimal approximate circular string matching","author":"C Barton","year":"2015","unstructured":"Barton C, Iliopoulos CS, Pissis SP. Language and automata theory and applications\u20149th international conference, LATA 2015, Proceedings. In: Dediu AH, Formenti E, Martin-Vide C, Truthe B, editors. Average-case optimal approximate circular string matching, vol. 8977, Lecture notes in computer science. Berlin: Springer; 2015. p. 85\u201396."},{"key":"76_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0960129515000134","volume":"FirstView","author":"T Athar","year":"2015","unstructured":"Athar T, Barton C, Bland W, Gao J, Iliopoulos CS, Liu C, Pissis SP. Fast circular dictionary-matching algorithm. Math Struct Comput Sci. 2015;FirstView:1\u201314. doi: 10.1017\/S0960129515000134 .","journal-title":"Math Struct Comput Sci"},{"issue":"2","key":"76_CR21","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. On a cyclic string-to-string correction problem. IPL. 1990;35(2):73\u20138.","journal-title":"IPL"},{"key":"76_CR22","first-page":"891","volume":"2","author":"A Marzal","year":"2000","unstructured":"Marzal A, Barrachina S. Speeding up the computation of the edit distance for cyclic strings. ICPR. 2000;2:891\u20134.","journal-title":"ICPR"},{"issue":"12","key":"76_CR23","doi-asserted-by":"crossref","first-page":"1797","DOI":"10.1016\/0031-3203(93)90177-X","volume":"26","author":"H Bunke","year":"1993","unstructured":"Bunke H, Buhler U. Applications of approximate string matching to 2D shape recognition. Pattern Recognit. 1993;26(12):1797\u2013812.","journal-title":"Pattern Recognit"},{"key":"76_CR24","first-page":"247","volume-title":"Accurate and efficient methods to improve multiple circular sequence alignment. In experimental algorithms\u201414th international symposium, SEA","author":"C Barton","year":"2015","unstructured":"Barton C, Iliopoulos CS, Kundu R, Pissis SP, Retha A, Vayani F. Proceedings of lecture notes in computer science. In: Bampis E, editor. Accurate and efficient methods to improve multiple circular sequence alignment. In experimental algorithms\u201414th international symposium, SEA, vol. 9125, Berlin: Springer; 2015. p. 247\u201358."},{"key":"76_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-10-230","volume":"10","author":"F Fernandes","year":"2009","unstructured":"Fernandes F, Pereira L, Freitas AT. CSA: an efficient algorithm to improve circular DNA multiple alignment. BMC Bioinform. 2009;10:1\u201313.","journal-title":"BMC Bioinform"},{"key":"76_CR26","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/j.tcs.2012.11.018","volume":"468","author":"T Lee","year":"2013","unstructured":"Lee T, Na JC, Park H, Park K, Sim JS. Finding consensus and optimal alignment of circular strings. Theor Comput Sci. 2013;468:92\u2013101.","journal-title":"Theor Comput Sci"},{"key":"76_CR27","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1002\/9780470892107.ch15","volume-title":"Algorithms in computational molecular biology","author":"N Pisanti","year":"2010","unstructured":"Pisanti N, Giraud M, Peterlongo P. Filters and seeds approaches for fast homology searches in large datasets. In: Elloumi M, Zomaya AY, editors. Algorithms in computational molecular biology. Hoboken: Wiley; 2010. p. 299\u2013320."},{"key":"76_CR28","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E Ukkonen","year":"1992","unstructured":"Ukkonen E. Approximate string-matching with $$q$$ q -grams and maximal matches. Theor Comput Sci. 1992;92:191\u2013211.","journal-title":"Theor Comput Sci"},{"key":"76_CR29","doi-asserted-by":"crossref","unstructured":"Burkhardt S, Crauser A, Ferragina P, Lenhof HP, Rivals E, Vingron M. $$q$$ q -gram based database searching using a suffix array (QUASAR). In: RECOMB \u201999 proceedings of the third annual international conference on Computational molecular biology. New York, NY: ACM; 1999. p. 77\u201383.","DOI":"10.1145\/299432.299460"},{"issue":"2","key":"76_CR30","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1089\/cmb.2006.13.296","volume":"13","author":"K Rasmussen","year":"2006","unstructured":"Rasmussen K, Stoye J, Myers E. Efficient $$q$$ q -gram filters for finding all epsilon-matches over a given length. J Comput Biol. 2006;13(2):296\u2013308.","journal-title":"J Comput Biol"},{"key":"76_CR31","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1748-7188-4-3","volume":"4","author":"P Peterlongo","year":"2009","unstructured":"Peterlongo P, Sacomoto GA, do Lago AP, Pisanti N, Sagot MF. Lossless filter for multiple repeats with bounded edit distance. Algorithm Mol Biol. 2009;4:3. doi: 10.1186\/1748-7188-4-3 .","journal-title":"Algorithm Mol Biol"},{"issue":"3","key":"76_CR32","first-page":"497","volume":"6","author":"P Peterlongo","year":"2008","unstructured":"Peterlongo P, Pisanti N, Boyer F, do Lago AP, Sagot MF. Lossless filter for multiple repetitions with hamming distance. JDA. 2008;6(3):497\u2013509.","journal-title":"JDA"},{"issue":"5","key":"76_CR33","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber U, Myers EW. Suffix arrays: a new method for on-line string searches. SIAM J Comput. 1993;22(5):935\u201348.","journal-title":"SIAM J Comput"},{"key":"76_CR34","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/978-3-662-48221-6_15","volume-title":"Algorithms in bioinformatics\u201415th international workshop, WABI 2015, Atlanta, GA, USA, September 10\u201312, 2015, Proceedings","author":"R Grossi","year":"2015","unstructured":"Grossi R, Iliopoulos CS, Mercas R, Pisanti N, Pissis SP, Retha A, Vayani F. Circular sequence comparison with q-grams. In: Pop M, Touzet H, editors. Algorithms in bioinformatics\u201415th international workshop, WABI 2015, Atlanta, GA, USA, September 10\u201312, 2015, Proceedings, vol. 9289, Lecture notes in computer science. Berlin: Springer; 2015. p. 203\u201316."},{"key":"76_CR35","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore M, Hancart C, Lecroq T. Algorithms on strings. New York: Cambridge University Press; 2007."},{"key":"76_CR36","doi-asserted-by":"crossref","unstructured":"Fischer J. Inducing the LCP-Array. In: Dehne F, Iacono J, Sack J-R, editors. 12th WADS, Volume 6844 of LNCS. 2011. p. 374\u201385.","DOI":"10.1007\/978-3-642-22300-6_32"},{"key":"76_CR37","doi-asserted-by":"crossref","unstructured":"Ehlers T, Manea F, Merca\u015f R, Nowotka D. $$k$$ k -Abelian pattern matching. In: Shur AM, Volkov MV, editors. 18th DLT, Volume 8633 of LNCS. 2014. p. 178\u201390.","DOI":"10.1007\/978-3-319-09698-8_16"},{"issue":"2","key":"76_CR38","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1142\/S0129054112400175","volume":"23","author":"P Burcsi","year":"2012","unstructured":"Burcsi P, Cicalese F, Fici G, Lipt\u00e1k Z. Algorithms for jumbled pattern matching in strings. Int J Found Comput Sci. 2012;23(2):357\u201374.","journal-title":"Int J Found Comput Sci"},{"issue":"3","key":"76_CR39","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. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970;48(3):443\u201353.","journal-title":"J Mol Biol"},{"issue":"3","key":"76_CR40","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh O. An improved algorithm for matching biological sequences. J Mol Biol. 1982;162(3):705\u20138.","journal-title":"J Mol Biol"},{"key":"76_CR41","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS. Identification of common molecular subsequences. J Mol Biol. 1981;147:195\u20137.","journal-title":"J Mol Biol"},{"issue":"8","key":"76_CR42","doi-asserted-by":"crossref","first-page":"1879","DOI":"10.1093\/molbev\/msp098","volume":"26","author":"W Fletcher","year":"2009","unstructured":"Fletcher W, Yang Z. INDELible: a flexible simulator of biological sequence evolution. Mol Biol Evol. 2009;26(8):1879\u201388.","journal-title":"Mol Biol Evol"},{"key":"76_CR43","doi-asserted-by":"crossref","unstructured":"Gog S, Beller T, Moffat A, Petri M. From theory to practice: plug and play with succinct data structures. In: Gudmundsson J, Katajainen J, editors. 13th international symposium on experimental algorithms, (SEA 2014). 2014. p. 326\u201337.","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"76_CR44","doi-asserted-by":"crossref","unstructured":"Wheeler TJ. Large-scale neighbor-joining with NINJA. In: Salzberg S, Warnow TJ, editors. Algorithms in bioinformatics, Springer; 2009. p. 375\u201389.","DOI":"10.1007\/978-3-642-04241-6_31"},{"key":"76_CR45","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"D Robinson","year":"1981","unstructured":"Robinson D, Foulds LR. Comparison of phylogenetic trees. Math Biosci. 1981;53:131\u201347.","journal-title":"Math Biosci"},{"issue":"12","key":"76_CR46","doi-asserted-by":"crossref","first-page":"1569","DOI":"10.1093\/bioinformatics\/btq228","volume":"26","author":"J Sukumaran","year":"2010","unstructured":"Sukumaran J, Holder MT. DendroPy: a python library for phylogenetic computing. Bioinformatics. 2010;26(12):1569\u201371.","journal-title":"Bioinformatics"},{"issue":"suppl 1","key":"76_CR47","doi-asserted-by":"crossref","first-page":"D61","DOI":"10.1093\/nar\/gkl842","volume":"35","author":"KD Pruitt","year":"2007","unstructured":"Pruitt KD, Tatusova T, Maglott DR. NCBI reference sequences (RefSeq): a curated non-redundant sequence database of genomes, transcripts and proteins. Nucleic Acids Res. 2007;35(suppl 1):D61\u20135.","journal-title":"Nucleic Acids Res"},{"key":"76_CR48","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0014-5793(95)01412-8","volume":"378","author":"A Rojas","year":"1996","unstructured":"Rojas A, Romeu A. A sequence analysis of the $$\\beta$$ \u03b2 -glucosidase sub-family B. FEBS Lett. 1996;378:93\u20137.","journal-title":"FEBS Lett"},{"issue":"Database issue","key":"76_CR49","doi-asserted-by":"publisher","first-page":"D204","DOI":"10.1093\/nar\/gku989","volume":"43","author":"UniProt Consortium","year":"2015","unstructured":"UniProt Consortium. UniProt: a hub for protein information. Nucleic Acids Res. 2015;43(Database issue):D204\u201312. doi: 10.1093\/nar\/gku989 .","journal-title":"Nucleic Acids Res"},{"issue":"suppl 1","key":"76_CR50","first-page":"D206","volume":"36","author":"CK Wang","year":"2008","unstructured":"Wang CK, Kaas Q, Chiche L, Craik DJ. CyBase: a database of cyclic protein sequences and structures, with applications in protein discovery and engineering. Nucleic Acids Res. 2008;36(suppl 1):D206\u201310.","journal-title":"Nucleic Acids Res"}],"updated-by":[{"DOI":"10.1186\/s13015-016-0084-6","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2016,7,27]],"date-time":"2016-07-27T00:00:00Z","timestamp":1469577600000}}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-016-0076-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T09:03:05Z","timestamp":1567846985000},"score":1,"resource":{"primary":{"URL":"http:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-016-0076-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,10]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["76"],"URL":"https:\/\/doi.org\/10.1186\/s13015-016-0076-6","relation":{"correction":[{"id-type":"doi","id":"10.1186\/s13015-016-0084-6","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,10]]},"article-number":"12"}}