{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T21:15:27Z","timestamp":1771103727031,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>The comparison of homologous sequences from different species is an essential approach to reconstruct the evolutionary history of species and of the genes they harbour in their genomes. Several complete mitochondrial and nuclear genomes are now available, increasing the importance of using multiple sequence alignment algorithms in comparative genomics. MtDNA has long been used in phylogenetic analysis and errors in the alignments can lead to errors in the interpretation of evolutionary information. Although a large number of multiple sequence alignment algorithms have been proposed to date, they all deal with linear DNA and cannot handle directly circular DNA. Researchers interested in aligning circular DNA sequences must first rotate them to the \"right\" place using an essentially manual process, before they can use multiple sequence alignment tools.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>In this paper we propose an efficient algorithm that identifies the most interesting region to cut circular genomes in order to improve phylogenetic analysis when using standard multiple sequence alignment algorithms. This algorithm identifies the largest chain of non-repeated longest subsequences common to a set of circular mitochondrial DNA sequences. All the sequences are then rotated and made linear for multiple alignment purposes.<\/jats:p>\n            <jats:p>To evaluate the effectiveness of this new tool, three different sets of mitochondrial DNA sequences were considered. Other tests considering randomly rotated sequences were also performed. The software package Arlequin was used to evaluate the standard genetic measures of the alignments obtained with and without the use of the CSA algorithm with two well known multiple alignment algorithms, the CLUSTALW and the MAVID tools, and also the visualization tool SinicView.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>The results show that a circularization and rotation pre-processing step significantly improves the efficiency of public available multiple sequence alignment algorithms when used in the alignment of circular DNA sequences. The resulting alignments lead to more realistic phylogenetic comparisons between species.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-10-230","type":"journal-article","created":{"date-parts":[[2009,8,6]],"date-time":"2009-08-06T18:17:56Z","timestamp":1249582676000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":39,"title":["CSA: An efficient algorithm to improve circular DNA multiple alignment"],"prefix":"10.1186","volume":"10","author":[{"given":"Francisco","family":"Fernandes","sequence":"first","affiliation":[]},{"given":"Lu\u00edsa","family":"Pereira","sequence":"additional","affiliation":[]},{"given":"Ana T","family":"Freitas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,7,23]]},"reference":[{"key":"2960_CR1","doi-asserted-by":"publisher","first-page":"3497","DOI":"10.1093\/nar\/gkg500","volume":"31","author":"R Chenna","year":"2003","unstructured":"Chenna R, Sugawara H, Koike T, Lopez R, Gibson TJ, Higgins DG, Thompson JD: Multiple sequence alignment with the Clustal series of programs. Nucleic Acids Res 2003, 31: 3497\u20133500.","journal-title":"Nucleic Acids Res"},{"key":"2960_CR2","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"JD Thompson","year":"1994","unstructured":"Thompson JD, Higgins DG, Gibson TJ: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice. Nucleic Acids Res 1994, 22: 4673\u20134680.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"2960_CR3","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame C, Higgins DG, Heringa J: T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol 2000, 302(1):205\u201317.","journal-title":"J Mol Biol"},{"key":"2960_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1186\/1471-2105-4-66","volume":"4","author":"M Brudno","year":"2003","unstructured":"Brudno M, Chapman M, G\u00f6ttgens B, Batzoglou S, Morgenstern B: Fast and sensitive multiple alignment of large genomic sequences. BMC Bioinformatics 2003, 4: 66.","journal-title":"BMC Bioinformatics"},{"issue":"5","key":"2960_CR5","doi-asserted-by":"publisher","first-page":"1792","DOI":"10.1093\/nar\/gkh340","volume":"32","author":"RC Edgar","year":"2004","unstructured":"Edgar RC: MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Res 2004, 32(5):1792\u20131797.","journal-title":"Nucleic Acids Res"},{"issue":"4","key":"2960_CR6","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1101\/gr.926603","volume":"13","author":"M Brudno","year":"2003","unstructured":"Brudno M, Do CB, Cooper GM, Kim MF, Davydov E, Green ED, Sidow A, Batzoglou S: LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA. Genome Res 2003, 13(4):721\u2013731.","journal-title":"Genome Res"},{"key":"2960_CR7","doi-asserted-by":"publisher","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: 693\u2013699.","journal-title":"Genome Res"},{"key":"2960_CR8","doi-asserted-by":"publisher","first-page":"1394","DOI":"10.1101\/gr.2289704","volume":"14","author":"AC Darling","year":"2004","unstructured":"Darling AC, Mau B, Blattner FR, Perna NT: Mauve: multiple alignment of conserved genomic sequence with rearrangements. Genome Res 2004, 14: 1394\u20131403.","journal-title":"Genome Res"},{"key":"2960_CR9","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1093\/oxfordjournals.molbev.a003825","volume":"18","author":"J Castresana","year":"2001","unstructured":"Castresana J: Cytochrome b phylogeny and the taxonomy of great apes and mammals. Mol Biol Evol 2001, 18: 465\u2013471.","journal-title":"Mol Biol Evol"},{"key":"2960_CR10","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1016\/S0002-9297(07)62954-1","volume":"67","author":"M Richards","year":"2000","unstructured":"Richards M, Macaulay V, Hickey E, Vega E, Sykes B, Guida V, Rengo C, Sellitto D, Cruciani F, Kivisild T, Villems R, Thomas M, Rychkov S, Rychkov O, Rychkov Y, G\u00f6lge M, Dimitrov D, Hill E, Bradley D, Romano V, Cal\u00ec F, Vona G, Demaine A, Papiha S, Triantaphyllidis C, Stefanescu G, Hatina J, Belledi M, Di Rienzo A, Novelletto A, Oppenheim A, N\u00f8rby S, Al-Zaheri N, Santachiara-Benerecetti S, Scozari R, Torroni A, Bandelt HJ: Tracing European founder lineages in the Near Eastern mtDNA pool. Am J Hum Genet 2000, 67: 1251\u20131276.","journal-title":"Am J Hum Genet"},{"key":"2960_CR11","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1016\/j.ajhg.2009.04.013","volume":"84","author":"L Pereira","year":"2009","unstructured":"Pereira L, Freitas F, Fernandes V, Pereira JB, Costa MD, Costa S, M\u00e1ximo V, Macaulay V, Rocha R, Samuels DC: The diversity present in 5,140 human mitochondrial genomes. Am J Hum Genet 2009, 84: 628\u2013640.","journal-title":"Am J Hum Genet"},{"key":"2960_CR12","doi-asserted-by":"publisher","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: 293\u2013298.","journal-title":"Genome Res"},{"key":"2960_CR13","series-title":"Nucleic Acids Res","first-page":"D25","volume-title":"GenBank","author":"DA Benson","year":"2008","unstructured":"Benson DA, Karsch-Mizrachi I, Lipman DJ, Ostell J, Wheeler DL: GenBank. Nucleic Acids Res 2008, (36 Database):D25\u201330."},{"key":"2960_CR14","series-title":"Nucleic Acids Res","first-page":"D61","volume-title":"NCBI reference sequences (RefSeq): a curated non-redundant sequence database of genomes, transcripts and proteins","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 Database):D61\u201365."},{"key":"2960_CR15","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1038\/290457a0","volume":"290","author":"S Anderson","year":"1981","unstructured":"Anderson S, Bankier AT, Barrell BG, de Bruijn MH, Coulson AR, Drouin J, Eperon IC, Nierlich DP, Roe BA, Sanger F, Schreier PH, Smith AJ, Staden R, Young IG: Sequence and organization of the human mitochondrial genome. Nature 1981, 290: 457\u2013465.","journal-title":"Nature"},{"issue":"2","key":"2960_CR16","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. Inform Process Lett 1990, 35(2):73\u201378.","journal-title":"Inform Process Lett"},{"issue":"3","key":"2960_CR17","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1142\/S0218001402001678","volume":"16","author":"RA Mollineda","year":"2002","unstructured":"Mollineda RA, Vidal E, Casacuberta F: Cyclic sequence alignments: approximate versus optimal techniques. Int J Patt Recogn and Artificial Intelligence 2002, 16(3):291\u2013299.","journal-title":"Int J Patt Recogn and Artificial Intelligence"},{"issue":"12","key":"2960_CR18","doi-asserted-by":"publisher","first-page":"1797","DOI":"10.1016\/0031-3203(93)90177-X","volume":"26","author":"H Bunke","year":"1993","unstructured":"Bunke H, B\u00fchler U: Applications of approximate string matching to 2D shape recognition. Patt Recogn 1993, 26(12):1797\u20131812.","journal-title":"Patt Recogn"},{"key":"2960_CR19","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/3-540-44522-6_35","volume-title":"Advances in Pattern Recognition","author":"RA Mollineda","year":"2000","unstructured":"Mollineda RA, Vidal E, Casacuberta F: Efficient techniques for a very accurate measurement of dissimilarities between cyclic patterns. In Advances in Pattern Recognition. Volume 1876. Lecture Notes in Computer Science. Springer; 2000:337\u2013346."},{"key":"2960_CR20","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.jtbi.2005.10.010","volume":"240","author":"G Fritzsch","year":"2006","unstructured":"Fritzsch G, Schlegel M, Stadler PF: Alignments of Mitochondrial Genome Arrangements: Applications to Metazoan Phylogeny. J Theor Biol 2006, 240: 511\u2013520.","journal-title":"J Theor Biol"},{"key":"2960_CR21","unstructured":"Mosig A, Hofacker IL, Stadler PF: Comparative Analysis of Cyclic Sequences: Viroids and other Small Circular RNAs. Proceedings of the German Conference on Bioinformatics: 20\u201322 September 2006; T\u00fcbingen P-83: 93\u2013102."},{"key":"2960_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/SWAT.1973.13","volume-title":"Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theor: 15\u201317 October 1973; Iowa","author":"P Weiner","year":"1973","unstructured":"Weiner P: Linear Pattern Matching Algorithm. Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theor: 15\u201317 October 1973; Iowa 1973, 1\u201311."},{"key":"2960_CR23","doi-asserted-by":"publisher","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: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. New York: Cambridge University Press; 1997."},{"issue":"3","key":"2960_CR24","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen E: On-line Construction of Suffix Trees. Algorithmica 1995, 14(3):249\u2013260.","journal-title":"Algorithmica"},{"key":"2960_CR25","first-page":"47","volume":"1","author":"L Excoffier","year":"2005","unstructured":"Excoffier L, Laval G, Schneider S: Arlequin ver. 3.0: An integrated software package for population genetics data analysis. Evolutionary Bioinformatics Online 2005, 1: 47\u201350.","journal-title":"Evolutionary Bioinformatics Online"},{"key":"2960_CR26","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1186\/1471-2105-7-103","volume":"7","author":"AC Shih","year":"2006","unstructured":"Shih AC, Lee DT, Lin L, Peng CL, Chen SH, Wu YW, Wong CY, Chou MY, Shiao TC, Hsieh MF: SinicView: a visualization environment for comparisons of multiple nucleotide sequence alignment tools. BMC Bioinformatics 2006, 7: 103.","journal-title":"BMC Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-10-230.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T21:33:13Z","timestamp":1630445593000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-10-230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,23]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["2960"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-10-230","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,23]]},"assertion":[{"value":"23 December 2008","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2009","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2009","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"230"}}