{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T21:39:15Z","timestamp":1778881155758,"version":"3.51.4"},"reference-count":41,"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>Multilocus Sequence Typing (MLST) is a frequently used typing method for the analysis of the clonal relationships among strains of several clinically relevant microbial species. MLST is based on the sequence of housekeeping genes that result in each strain having a distinct numerical allelic profile, which is abbreviated to a unique identifier: the sequence type (ST). The relatedness between two strains can then be inferred by the differences between allelic profiles. For a more comprehensive analysis of the possible patterns of evolutionary descent, a set of rules were proposed and implemented in the eBURST algorithm. These rules allow the division of a data set into several clusters of related strains, dubbed clonal complexes, by implementing a simple model of clonal expansion and diversification. Within each clonal complex, the rules identify which links between STs correspond to the most probable pattern of descent. However, the eBURST algorithm is not globally optimized, which can result in links, within the clonal complexes, that violate the rules proposed.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>Here, we present a globally optimized implementation of the eBURST algorithm \u2013 goeBURST. The search for a global optimal solution led to the formalization of the problem as a graphic matroid, for which greedy algorithms that provide an optimal solution exist. Several public data sets of MLST data were tested and differences between the two implementations were found and are discussed for five bacterial species: <jats:italic>Enterococcus faecium<\/jats:italic>, <jats:italic>Streptococcus pneumoniae<\/jats:italic>, <jats:italic>Burkholderia pseudomallei<\/jats:italic>, <jats:italic>Campylobacter jejuni<\/jats:italic> and <jats:italic>Neisseria spp.<\/jats:italic>. A novel feature implemented in goeBURST is the representation of the level of tiebreak rule reached before deciding if a link should be drawn, which can used to visually evaluate the reliability of the represented hypothetical pattern of descent.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>goeBURST is a globally optimized implementation of the eBURST algorithm, that identifies alternative patterns of descent for several bacterial species. Furthermore, the algorithm can be applied to any multilocus typing data based on the number of differences between numeric profiles. A software implementation is available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/goeBURST.phyloviz.net\" ext-link-type=\"uri\">http:\/\/goeBURST.phyloviz.net<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-10-152","type":"journal-article","created":{"date-parts":[[2009,5,19]],"date-time":"2009-05-19T07:27:56Z","timestamp":1242718076000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":545,"title":["Global optimal eBURST analysis of multilocus typing data using a graphic matroid approach"],"prefix":"10.1186","volume":"10","author":[{"given":"Alexandre P","family":"Francisco","sequence":"first","affiliation":[]},{"given":"Miguel","family":"Bugalho","sequence":"additional","affiliation":[]},{"given":"M\u00e1rio","family":"Ramirez","sequence":"additional","affiliation":[]},{"given":"Jo\u00e3o A","family":"Carri\u00e7o","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,18]]},"reference":[{"issue":"6","key":"2882_CR1","doi-asserted-by":"publisher","first-page":"3140","DOI":"10.1073\/pnas.95.6.3140","volume":"95","author":"MCJ Maiden","year":"1998","unstructured":"Maiden MCJ, Bygraves JA, Feil E, Morelli G, Russell JE, Urwin R, Zhang Q, Zhou J, Zurth K, Caugant DA, et al.: Multilocus sequence typing: A portable approach to the identification of clones within populations of pathogenic microorganisms. Proceedings of the National Academy of Sciences 1998, 95(6):3140\u20133145. 10.1073\/pnas.95.6.3140","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2882_CR2","unstructured":"MLST: Multi Locus Sequence TypingImperial College of London; [http:\/\/www.mlst.net]"},{"key":"2882_CR3","unstructured":"PubMLSTUniversity of Oxford (UK); [http:\/\/pubmlst.org\/]"},{"key":"2882_CR4","unstructured":"Institut Pasteur MLST DatabasesPasteur Institute; [http:\/\/www.pasteur.fr\/mlst\/]"},{"key":"2882_CR5","unstructured":"Ec MLSTMichigan State University; [http:\/\/www.shigatox.net\/cgi-bin\/mlst7\/index]"},{"key":"2882_CR6","first-page":"7687","volume-title":"Proceedings of the National Academy of Sciences","author":"MC Enright","year":"2002","unstructured":"Enright MC, Robinson DA, Randle G, Feil EJ, Grundmann H, Spratt BG: The evolutionary history of methicillin-resistant Staphylococcus aureus (MRSA). Proceedings of the National Academy of Sciences 2002, 7687\u20137692. 10.1073\/pnas.122108599"},{"issue":"11","key":"2882_CR7","doi-asserted-by":"publisher","first-page":"3049","DOI":"10.1099\/00221287-144-11-3049","volume":"144","author":"MC Enright","year":"1998","unstructured":"Enright MC, Spratt BG: A multilocus sequence typing scheme for Streptococcus pneumoniae: identification of clones associated with serious invasive disease. Microbiology 1998, 144(11):3049\u20133060. 10.1099\/00221287-144-11-3049","journal-title":"Microbiology"},{"issue":"5","key":"2882_CR8","doi-asserted-by":"publisher","first-page":"1518","DOI":"10.1128\/JB.186.5.1518-1530.2004","volume":"186","author":"EJ Feil","year":"2004","unstructured":"Feil EJ, Li BC, Aanensen DM, Hanage WP, Spratt BG: eBURST: Inferring Patterns of Evolutionary Descent among Clusters of Related Bacterial Genotypes from Multilocus Sequence Typing Data. Journal of Bacteriology 2004, 186(5):1518\u20131530. 10.1128\/JB.186.5.1518-1530.2004","journal-title":"Journal of Bacteriology"},{"issue":"3","key":"2882_CR9","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.annepidem.2005.04.010","volume":"16","author":"BG Hall","year":"2006","unstructured":"Hall BG, Barlow M: Phylogenetic Analysis as a Tool in Molecular Epidemiology of Infectious Diseases. Annals of Epidemiology 2006, 16(3):157\u2013169. 10.1016\/j.annepidem.2005.04.010","journal-title":"Annals of Epidemiology"},{"issue":"6","key":"2882_CR10","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1038\/nrmicro1872","volume":"6","author":"M Achtman","year":"2008","unstructured":"Achtman M, Wagner M: Microbial diversity and the genetic nature of microbial species. Nature Reviews Microbiology 2008, 6(6):431. 10.1038\/nrmicro1872","journal-title":"Nature Reviews Microbiology"},{"key":"2882_CR11","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1093\/molbev\/msj030","volume":"23","author":"DH Huson","year":"2006","unstructured":"Huson DH, Bryant D: Application of phylogenetic networks in evolutionay studies. Molecular Biology and Evolution 2006, 23: 254\u2013267. 10.1093\/molbev\/msj030","journal-title":"Molecular Biology and Evolution"},{"issue":"6","key":"2882_CR12","doi-asserted-by":"publisher","first-page":"1893","DOI":"10.1099\/ijs.0.02713-0","volume":"53","author":"DR Zeigler","year":"2003","unstructured":"Zeigler DR: Gene sequences useful for predicting relatedness of whole genomes in bacteria. International Journal of Systematic and Evolutionary Microbiology 2003, 53(6):1893\u20131900. 10.1099\/ijs.0.02713-0","journal-title":"International Journal of Systematic and Evolutionary Microbiology"},{"key":"2882_CR13","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1038\/nrmicro1236","volume":"3","author":"D Gevers","year":"2005","unstructured":"Gevers D, Cohan FM, Lawrence JG, Spratt BG, Coenye T, Feil EJ, e Stackebrandt, de Peer YV, Vandamme P, F LT, Swings J: Re-evaluating prokaryotic species. Nature Reviews Microbiology 2005, 3: 733\u2013739. 10.1038\/nrmicro1236","journal-title":"Nature Reviews Microbiology"},{"issue":"3","key":"2882_CR14","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1534\/genetics.106.063305","volume":"175","author":"X Didelot","year":"2007","unstructured":"Didelot X, Falush D: Inference of Bacterial Microevolution Using Multilocus Sequence Data. Genetics 2007, 175(3):1251. 10.1534\/genetics.106.063305","journal-title":"Genetics"},{"key":"2882_CR15","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1073\/pnas.98.1.182","volume":"98","author":"EJ Feil","year":"2001","unstructured":"Feil EJ, Holmes EC, Bessen DE, Chan MS, Day NPJ, Enright MC, Goldstein R, Hood DW, Kalia A, Moore CE, et al.: Recombination within natural populations of pathogenic bacteria: Short-term empirical estimates and long-term phylogenetic consequences. Proceedings of the National Academy of Sciences 2001, 98: 182. 10.1073\/pnas.98.1.182","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2882_CR16","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1002\/1521-1878(200012)22:12<1115::AID-BIES9>3.0.CO;2-R","volume":"22","author":"JM Smith","year":"2000","unstructured":"Smith JM, Feil EJ, Smith NH: Population structure and evolutionay dynamics of pathogenic bacteria. BioEssays 2000, 22: 1115\u20131122. 10.1002\/1521-1878(200012)22:12<1115::AID-BIES9>3.0.CO;2-R","journal-title":"BioEssays"},{"key":"2882_CR17","unstructured":"eBURST V3 readme fileImperial College of London; [http:\/\/eburst.mlst.net\/documents\/eBURST_readme_v3.pdf]"},{"key":"2882_CR18","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1186\/1471-2180-8-198","volume":"8","author":"M Antonio","year":"2008","unstructured":"Antonio M, Hakeem I, Awine T, Secka O, Sankareh K, Nsekpong D, Lahai G, Akisanya A, Egere U, Enwere G, Zaman SMA, Hill PC, Corrah T, Cutts F, Greenwood BM, Adegbola RA: Seasonality and outbreak of a predominant Streptococcus pneumoniae serotype 1 clone from The Gambia: Expansion of ST217 hypervirulent clonal complex in West Africa. BMC Microbiology 2008, 8: 198. 10.1186\/1471-2180-8-198","journal-title":"BMC Microbiology"},{"key":"2882_CR19","doi-asserted-by":"publisher","first-page":"5496","DOI":"10.1128\/JB.186.16.5496-5505.2004","volume":"186","author":"LM Schouls","year":"2004","unstructured":"Schouls LM, Heide HG, Vauterin L, Vauterin P, Mooi FR: Multiple-locus variable-number tandem repeat analysis of Dutch Bordetella pertussis strains reveals rapid genetic changes with clonal expansion during the late 1990s. Journal of Bacteriology 2004, 186: 5496\u20135505. 10.1128\/JB.186.16.5496-5505.2004","journal-title":"Journal of Bacteriology"},{"key":"2882_CR20","doi-asserted-by":"publisher","first-page":"1964","DOI":"10.1128\/AAC.01487-07","volume":"52","author":"EG de la Pedrosa","year":"2008","unstructured":"de la Pedrosa EG, Morosini MI, Linden M, Ruiz-Garbajosa P, Galan JC, Baquero F, Reinert RR, Canton R: Polyclonal population structure of Streptococcus pneumoniae isolates in Spain carrying mef and mef plus erm(B). Antimicrobial Agents and Chemotherapy 2008, 52: 1964\u20131969. 10.1128\/AAC.01487-07","journal-title":"Antimicrobial Agents and Chemotherapy"},{"key":"2882_CR21","doi-asserted-by":"publisher","first-page":"2220","DOI":"10.1128\/JCM.02596-05","volume":"44","author":"P Ruiz-Garbajosa","year":"2006","unstructured":"Ruiz-Garbajosa P, Bonten MJ, Robinson DA, Top J, Nallapareddy SR, Torres C, Coque TM, Canton R, Baquero F, Murray BE, del Campo R, Willems RJ: Multilocus sequence typing scheme for Entrococcus faecalis reveals hospital-adapted genetic complexes in a background of high rates of recombination. Journal of Clinical Microbiology 2006, 44: 2220\u20132228. 10.1128\/JCM.02596-05","journal-title":"Journal of Clinical Microbiology"},{"key":"2882_CR22","volume-title":"Prace Morask\u00e9 Pridovedeck\u00e9 Spolecnosti","author":"O Boruvka","year":"1926","unstructured":"Boruvka O: On a minimal problem. Prace Morask\u00e9 Pridovedeck\u00e9 Spolecnosti 1926., 3:"},{"key":"2882_CR23","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal JB: On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 1956, 7: 48\u201350. 10.2307\/2033241","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2882_CR24","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C: Introduction to Algorithms. MIT Press; 2001."},{"key":"2882_CR25","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-540-31292-5_6","volume-title":"Molecular identification, systematics, and population structure of prokaryotes","author":"L Vauterin","year":"2006","unstructured":"Vauterin L, Vauterin P: Integrated databasing and analysis. In Molecular identification, systematics, and population structure of prokaryotes. Edited by: Stackebrandt E. Springer-Verlag; 2006:141\u2013217."},{"key":"2882_CR26","volume-title":"Combinatorial Optimization. Dover","author":"CH Papadimitriou","year":"1998","unstructured":"Papadimitriou CH, Steiglitz K: Combinatorial Optimization. Dover. 1998."},{"issue":"3","key":"2882_CR27","doi-asserted-by":"publisher","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H Whitney","year":"1935","unstructured":"Whitney H: On the abstract properties of linear dependence. American Journal of Mathematics 1935, 57(3):509\u2013533. 10.2307\/2371182","journal-title":"American Journal of Mathematics"},{"key":"2882_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.6028\/jres.069B.001","volume":"69","author":"WT Tutte","year":"1965","unstructured":"Tutte WT: Lectures on matroids. J Res Nat Bur Standards Sect B 1965, 69: 1\u201347.","journal-title":"J Res Nat Bur Standards Sect B"},{"key":"2882_CR29","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J Edmonds","year":"1971","unstructured":"Edmonds J: Matroids and the greedy algorithm. Mathematical Programming 1971, 1: 127\u2013136. 10.1007\/BF01584082","journal-title":"Mathematical Programming"},{"key":"2882_CR30","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1128\/JCM.01351-07","volume":"46","author":"J Top","year":"2008","unstructured":"Top J, Willems R, Velden S, Asbroek M, Bonten M: Emergence of Clonal Complex 17 Enterococcus faecium in The Netherlands. Journal of Clinical Microbiology 2008, 46: 214. 10.1128\/JCM.01351-07","journal-title":"Journal of Clinical Microbiology"},{"issue":"6","key":"2882_CR31","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1093\/jac\/dkn390","volume":"62","author":"MJA de Regt","year":"2008","unstructured":"de Regt MJA, Wagen LE, Top J, Blok HEM, Hopmans TEM, Dekker AW, Hene RJ, Siersema PD, Willems RJL, Bonten MJM: High acquisition and environmental contamination rates of CC17 ampicillin-resistant Enterococcus faecium in a Dutch hospital. Journal of Antimicrobial Chemotherapy 2008, 62(6):1401\u20131406. 10.1093\/jac\/dkn390","journal-title":"Journal of Antimicrobial Chemotherapy"},{"key":"2882_CR32","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1093\/jac\/dkn449","volume":"63","author":"S Valdezate","year":"2009","unstructured":"Valdezate S, Labayru C, Navarro A, Mantecon MA, Ortega M, Coque TM, Garcia M, Saez-Nieto JA: Large clonal outbreak of multidrug-resistant CC17 ST17 Enterococcus faecium containing Tn5382 in a Spanish hospital. Journal of Antimicrobial Chemotherapy 2009, 63: 17. 10.1093\/jac\/dkn449","journal-title":"Journal of Antimicrobial Chemotherapy"},{"issue":"10","key":"2882_CR33","doi-asserted-by":"publisher","first-page":"1812","DOI":"10.3201\/eid1010.040335","volume":"10","author":"AJ Pollard","year":"2004","unstructured":"Pollard AJ, Ochnio J, Ho M, Callaghan M, Bigham M, Dobson S: Disease susceptibility to ST11 complex meningococci bearing serogroup C or W135 polysaccharide capsules, North America. Emerging Infectious Diseases 2004, 10(10):1812\u20131815.","journal-title":"Emerging Infectious Diseases"},{"issue":"10","key":"2882_CR34","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1016\/S1473-3099(06)70584-9","volume":"6","author":"CL Trotter","year":"2006","unstructured":"Trotter CL, Ramsay ME, Gray S, Fox A, Kaczmarski E: No evidence for capsule replacement following mass immunisation with meningococcal serogroup C conjugate vaccines in England and Wales. The Lancet Infectious Diseases 2006, 6(10):616\u2013617. 10.1016\/S1473-3099(06)70584-9","journal-title":"The Lancet Infectious Diseases"},{"key":"2882_CR35","unstructured":"The Prefuse visualization toolkitBerkeley Institute of Design; [http:\/\/prefuse.org\/]"},{"key":"2882_CR36","unstructured":"FreeHEP Java LibrariesSLAC \u2013 Stanford Linear Accelerator Center; [http:\/\/java.freehep.org\/]"},{"key":"2882_CR37","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1186\/1471-2180-7-30","volume":"7","author":"KME Turner","year":"2007","unstructured":"Turner KME, Hanage WP, Fraser C, Connor TR, Spratt BG: Assessing the reliability of eBURST using simulated populations with known ancestry. BMC Microbiology 2007, 7: 30. 10.1186\/1471-2180-7-30","journal-title":"BMC Microbiology"},{"key":"2882_CR38","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1146\/annurev.micro.62.081307.162832","volume":"62","author":"M Achtman","year":"2008","unstructured":"Achtman M: Evolution, population structure, and phylogeography of genetically monomorphic bacterial pathogens. Annu Rev Microbiol 2008, 62: 53\u201370. 10.1146\/annurev.micro.62.081307.162832","journal-title":"Annu Rev Microbiol"},{"key":"2882_CR39","doi-asserted-by":"crossref","unstructured":"Dos Vultos T, Mestre O, Rauzier J, Golec M, Rastogi N, Rasolofo V, Tonjum T, Sola C, Matic I, Gicquel B: Evolution and Diversity of Clonal Bacteria: The Paradigm of Mycobacterium tuberculosis. PLoS ONE 2008., 3(2): 10.1371\/journal.pone.0001538","DOI":"10.1371\/journal.pone.0001538"},{"issue":"5803","key":"2882_CR40","doi-asserted-by":"publisher","first-page":"1301","DOI":"10.1126\/science.1134933","volume":"314","author":"P Roumagnac","year":"2006","unstructured":"Roumagnac P, Weill F, Dolecek C, Baker S, Brisse S, Chinh N, Le T, Acosta C, Farrar J, Dougan G, et al.: Evolutionary history of Salmonella typhi. Science 2006, 314(5803):1301\u20131304. 10.1126\/science.1134933","journal-title":"Science"},{"issue":"37","key":"2882_CR41","doi-asserted-by":"publisher","first-page":"14130","DOI":"10.1073\/pnas.0804178105","volume":"105","author":"U N\u00fcbel","year":"2008","unstructured":"N\u00fcbel U, Roumagnac P, Feldkamp M, Song J, Ko K, Huang Y, Coombs G, Ip M, Westh H, Skov R, et al.: Frequent emergence and limited geographic dispersal of methicillin-resistant Staphylococcus aureus. Proceedings of the National Academy of Sciences 2008, 105(37):14130. 10.1073\/pnas.0804178105","journal-title":"Proceedings of the National Academy of Sciences"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-10-152.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T21:40:38Z","timestamp":1630446038000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-10-152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,18]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["2882"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-10-152","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,18]]},"assertion":[{"value":"13 March 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2009","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2009","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"152"}}