{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T13:49:24Z","timestamp":1762004964638,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["TUBITAK\/0004\/2014","LISBOA-01-0145-FEDER-016394","LISBOA-01-0145-FEDER-016417","UID\/CEC\/500021\/2013"],"award-info":[{"award-number":["TUBITAK\/0004\/2014","LISBOA-01-0145-FEDER-016394","LISBOA-01-0145-FEDER-016417","UID\/CEC\/500021\/2013"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Royal Society International Exchanges Scheme"},{"DOI":"10.13039\/100014803","name":"European Food Safety Authority","doi-asserted-by":"crossref","award":["GP\/EFSA\/AFSCO\/2015\/01\/CT2"],"award-info":[{"award-number":["GP\/EFSA\/AFSCO\/2015\/01\/CT2"]}],"id":[{"id":"10.13039\/100014803","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1186\/s13015-017-0119-7","type":"journal-article","created":{"date-parts":[[2018,2,15]],"date-time":"2018-02-15T04:40:05Z","timestamp":1518669605000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Fast phylogenetic inference from typing data"],"prefix":"10.1186","volume":"13","author":[{"given":"Jo\u00e3o A.","family":"Carri\u00e7o","sequence":"first","affiliation":[]},{"given":"Maxime","family":"Crochemore","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4852-1641","authenticated-orcid":false,"given":"Alexandre P.","family":"Francisco","sequence":"additional","affiliation":[]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[]},{"given":"Bruno","family":"Ribeiro-Gon\u00e7alves","sequence":"additional","affiliation":[]},{"given":"C\u00e1tia","family":"Vaz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,15]]},"reference":[{"issue":"6","key":"119_CR1","doi-asserted-by":"publisher","first-page":"3140","DOI":"10.1073\/pnas.95.6.3140","volume":"95","author":"MC Maiden","year":"1998","unstructured":"Maiden MC, Bygraves JA, Feil EJ, Morelli G, Russell JE, Urwin R, Zhang Q, Zhou J, Zurth K, Caugant DA, Feavers IM, Achtman M, Spratt BG. Multilocus sequence typing: a portable approach to the identification of clones within populations of pathogenic microorganisms. Proc Natl Acad Sci USA. 1998;95(6):3140\u20135.","journal-title":"Proc Natl Acad Sci USA"},{"key":"119_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974076","volume-title":"Phylogenetic networks: concepts, algorithms and applications","author":"DH Huson","year":"2010","unstructured":"Huson DH, Rupp R, Scornavacca C. Phylogenetic networks: concepts, algorithms and applications. New York: Cambridge University Press; 2010. \n                    https:\/\/doi.org\/10.1017\/CBO9780511974076\n                    \n                  ."},{"key":"119_CR3","doi-asserted-by":"publisher","DOI":"10.1002\/9780470600122","volume-title":"Bacterial population genetics in infectious disease","author":"DA Robinson","year":"2010","unstructured":"Robinson DA, Feil EJ. Bacterial population genetics in infectious disease. Hoboken: Wiley; 2010. \n                    https:\/\/doi.org\/10.1002\/9780470600122\n                    \n                  ."},{"key":"119_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5304-7","volume-title":"Introduction to evolutionary genomics","author":"N Saitou","year":"2013","unstructured":"Saitou N. Introduction to evolutionary genomics. London: Springer; 2013. \n                    https:\/\/doi.org\/10.1007\/978-1-4471-5304-7\n                    \n                  ."},{"issue":"5","key":"119_CR5","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1089\/106652702761034136","volume":"9","author":"R Desper","year":"2002","unstructured":"Desper R, Gascuel O. Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. J Comput Biol. 2002;9(5):687\u2013705. \n                    https:\/\/doi.org\/10.1089\/106652702761034136\n                    \n                  .","journal-title":"J Comput Biol"},{"key":"119_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-800049-6.00206-7","volume-title":"Encyclopedia of evolutionary biology","author":"F Pardi","year":"2016","unstructured":"Pardi F, Gascuel O. Distance-based methods in phylogenetics. In: Encyclopedia of evolutionary biology. Oxford: Elsevier; 2016. p. 458\u201365. \n                    https:\/\/doi.org\/10.1016\/B978-0-12-800049-6.00206-7\n                    \n                  ."},{"issue":"1","key":"119_CR7","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 M-S, Day NP, 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. Proc Natl Acad Sci. 2001;98(1):182\u20137. \n                    https:\/\/doi.org\/10.1073\/pnas.98.1.182\n                    \n                  .","journal-title":"Proc Natl Acad Sci"},{"issue":"5","key":"119_CR8","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1038\/nrg3186","volume":"13","author":"Z Yang","year":"2012","unstructured":"Yang Z, Rannala B. Molecular phylogenetics: principles and practice. Nat Rev Genet. 2012;13(5):303\u201314.","journal-title":"Nat Rev Genet"},{"issue":"5","key":"119_CR9","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. J Bacteriol. 2004;186(5):1518\u201330. \n                    https:\/\/doi.org\/10.1128\/JB.186.5.1518-1530.2004\n                    \n                  .","journal-title":"J Bacteriol"},{"issue":"1","key":"119_CR10","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1186\/1471-2105-10-152","volume":"10","author":"AP Francisco","year":"2009","unstructured":"Francisco AP, Bugalho M, Ramirez M. Global optimal eBURST analysis of multilocus typing data using a graphic matroid approach. BMC Bioinform. 2009;10(1):152. \n                    https:\/\/doi.org\/10.1186\/1471-2105-10-152\n                    \n                  .","journal-title":"BMC Bioinform"},{"issue":"4","key":"119_CR11","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1093\/oxfordjournals.molbev.a040454","volume":"4","author":"N Saitou","year":"1987","unstructured":"Saitou N, Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol. 1987;4(4):406\u201325. \n                    https:\/\/doi.org\/10.1093\/oxfordjournals.molbev.a040454\n                    \n                  .","journal-title":"Mol Biol Evol"},{"key":"119_CR12","first-page":"1409","volume":"38","author":"RR Sokal","year":"1958","unstructured":"Sokal RR. A statistical method for evaluating systematic relationships. Univ Kans Sci Bull. 1958;38:1409\u201338.","journal-title":"Univ Kans Sci Bull"},{"key":"119_CR13","unstructured":"Sergean M, Zhou Z, Alikhan NF, Achtman M. EnteroBase. \n                    https:\/\/enterobase.warwick.ac.uk\/\n                    \n                  . Accessed 31 Oct 2017."},{"key":"119_CR14","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1186\/1471-2105-11-595","volume":"11","author":"KA Jolley","year":"2010","unstructured":"Jolley KA, Maiden MCJ. BIGSdb: scalable analysis of bacterial genome variation at the population level. BMC Bioinform. 2010;11:595.","journal-title":"BMC Bioinform"},{"key":"119_CR15","doi-asserted-by":"publisher","unstructured":"Crochemore M, Francisco AP, Pissis SP, Vaz C. Towards distance-based phylogenetic inference in average-case linear-time. In: Schwartz R, Reinert K (eds.) 17th international workshop on algorithms in bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 88, p. 9\u20131914. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. 2017. \n                    https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2017.9\n                    \n                  . \n                    http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7652\n                    \n                  .","DOI":"10.4230\/LIPIcs.WABI.2017.9"},{"issue":"5","key":"119_CR16","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber U, Myers G. Suffix arrays: a new method for on-line string searches. SIAM J Comput. 1993;22(5):935\u201348. \n                    https:\/\/doi.org\/10.1137\/0222058\n                    \n                  .","journal-title":"SIAM J Comput"},{"key":"119_CR17","doi-asserted-by":"publisher","unstructured":"Bender MA, Farach-Colton M. The LCA problem revisited. In: LATIN 2000: theoretical informatics: 4th Latin American symposium. Lecture notes in computer Sscience, vol. 1776, p. 88\u201394. Springer, Berlin, Heidelberg. 2000. \n                    https:\/\/doi.org\/10.1007\/10719839_9\n                    \n                  .","DOI":"10.1007\/10719839_9"},{"issue":"2","key":"119_CR18","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"MA Bender","year":"2005","unstructured":"Bender MA, Farach-Colton M, Pemmasani G, Skiena S, Sumazin P. Lowest common ancestors in trees and directed acyclic graphs. J Algorithms. 2005;57(2):75\u201394. \n                    https:\/\/doi.org\/10.1016\/j.jalgor.2005.08.001\n                    \n                  .","journal-title":"J Algorithms"},{"issue":"6","key":"119_CR19","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen J, Sanders P, Burkhardt S. Linear work suffix array construction. J ACM. 2006;53(6):918\u201336. \n                    https:\/\/doi.org\/10.1145\/1217856.1217858\n                    \n                  .","journal-title":"J ACM"},{"key":"119_CR20","doi-asserted-by":"publisher","unstructured":"Ko P, Aluru S. Space efficient linear time construction of suffix arrays. In: Annual symposium on combinatorial pattern matching. Lecture notes in computer science, vol. 2676, p. 200\u201310. Springer, Berlin, Heidelberg. 2003. \n                    https:\/\/doi.org\/10.1016\/j.jda.2004.08.002\n                    \n                  .","DOI":"10.1016\/j.jda.2004.08.002"},{"key":"119_CR21","doi-asserted-by":"publisher","unstructured":"Kasai T, Lee G, Arimura H, Arikawa S, Park K. Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Annual symposium on combinatorial pattern matching. Springer. 2001. p. 181\u201392. \n                    https:\/\/doi.org\/10.1007\/3-540-48194-X\n                    \n                  .","DOI":"10.1007\/3-540-48194-X"},{"key":"119_CR22","volume-title":"Combinatorial optimization: algorithms and complexity","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou CH, Steiglitz K. Combinatorial optimization: algorithms and complexity. Upper Saddle River: Prentice-Hall Inc; 1982."},{"issue":"1","key":"119_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. Proc Am Math Soc. 1956;7(1):48\u201350. \n                    https:\/\/doi.org\/10.2307\/2033241\n                    \n                  .","journal-title":"Proc Am Math Soc"},{"key":"119_CR24","unstructured":"B-UMMI: INNUENDO platform. \n                    https:\/\/github.com\/B-UMMI\/INNUENDO\n                    \n                  . Accessed 31 Oct 2017."},{"key":"119_CR25","unstructured":"INNUENDO: a novel cross-sectorial platform for the integration of genomics in surveillance of foodborne pathogens. \n                    http:\/\/www.innuendoweb.org\/\n                    \n                  . Accessed 31 Oct 2017."},{"issue":"Webserver\u2013Issue","key":"119_CR26","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1093\/nar\/gkw359","volume":"44","author":"B Ribeiro-Gon\u00e7alves","year":"2016","unstructured":"Ribeiro-Gon\u00e7alves B, Francisco AP, Vaz C, Ramirez M, Carri\u00e7o JA. PHYLOViZ online: web-based tool for visualization, phylogenetic inference, analysis and sharing of minimum spanning trees. Nucleic Acids Res. 2016;44(Webserver\u2013Issue):246\u201351. \n                    https:\/\/doi.org\/10.1093\/nar\/gkw359\n                    \n                  .","journal-title":"Nucleic Acids Res"},{"key":"119_CR27","unstructured":"B-UMMI: fast MLST searching and querying. \n                    https:\/\/github.com\/B-UMMI\/fast-mlst\n                    \n                  . Accessed 31 Oct 2017."},{"key":"119_CR28","unstructured":"Mori Y. A lightweight suffix-sorting library. \n                    https:\/\/github.com\/y-256\/libdivsufsort\n                    \n                  . Accessed 31 Oct 2017."},{"key":"119_CR29","unstructured":"Larsson NJ, Sadakane K. Suffix sorting implementation to accompany the paper Faster Suffix Sorting. \n                    http:\/\/www.larsson.dogma.net\/qsufsort.c\n                    \n                  . Accessed 31 Oct 2017."},{"issue":"3","key":"119_CR30","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.tcs.2007.07.017","volume":"387","author":"NJ Larsson","year":"2007","unstructured":"Larsson NJ, Sadakane K. Faster suffix sorting. Theor Comput Sci. 2007;387(3):258\u201372. \n                    https:\/\/doi.org\/10.1016\/j.tcs.2007.07.017\n                    \n                  .","journal-title":"Theor Comput Sci"},{"issue":"1","key":"119_CR31","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1186\/1471-2105-13-87","volume":"13","author":"AP Francisco","year":"2012","unstructured":"Francisco AP, Vaz C, Monteiro PT, Melo-Cristino J, Ramirez M, Carri\u00e7o JA. PHYLOViZ: phylogenetic inference and data visualization for sequence based typing methods. BMC Bioinform. 2012;13(1):87. \n                    https:\/\/doi.org\/10.1186\/1471-2105-13-87\n                    \n                  .","journal-title":"BMC Bioinform"},{"key":"119_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1005813.1041513","volume":"9","author":"K Fredriksson","year":"2004","unstructured":"Fredriksson K. Average-optimal single and multiple approximate string matching. ACM J Exp Algorithm. 2004;9:1\u20134. \n                    https:\/\/doi.org\/10.1145\/1005813.1041513\n                    \n                  .","journal-title":"ACM J Exp Algorithm"},{"key":"119_CR33","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1186\/1748-7188-9-9","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:9. \n                    https:\/\/doi.org\/10.1186\/1748-7188-9-9\n                    \n                  .","journal-title":"Algorithms Mol Biol"},{"key":"119_CR34","doi-asserted-by":"publisher","unstructured":"Munro JI, Nekrich Y, Vitter JS. Dynamic data structures for document collections and graphs. In: Proceedings of the 34th ACM symposium on principles of database systems. ACM, New York, NY, USA. 2015. \n                    https:\/\/doi.org\/10.1145\/2745754.2745778\n                    \n                  .","DOI":"10.1145\/2745754.2745778"},{"issue":"1","key":"119_CR35","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1093\/bioinformatics\/btw582","volume":"33","author":"M Nascimento","year":"2017","unstructured":"Nascimento M, Sousa A, Ramirez M, Francisco AP, Carri\u00e7o JA, Vaz C. PHYLOViZ 2.0: providing scalable data integration and visualization for multiple phylogenetic inference methods. Bioinformatics. 2017;33(1):128\u20139. \n                    https:\/\/doi.org\/10.1093\/bioinformatics\/btw582\n                    \n                  .","journal-title":"Bioinformatics"},{"issue":"4","key":"119_CR36","doi-asserted-by":"publisher","first-page":"e000056","DOI":"10.1099\/mgen.0.000056","volume":"2","author":"AJ Page","year":"2016","unstructured":"Page AJ, Taylor B, Delaney AJ, Soares J, Seemann T, Keane JA, Harris SR. SNP-sites: rapid efficient extraction of SNPs from multi-FASTA alignments. Microbial Genom. 2016;2(4):e000056. \n                    https:\/\/doi.org\/10.1099\/mgen.0.000056\n                    \n                  .","journal-title":"Microbial Genom"},{"issue":"6","key":"119_CR37","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1038\/ng.2625","volume":"45","author":"NJ Croucher","year":"2013","unstructured":"Croucher NJ, Finkelstein JA, Pelton SI, Mitchell PK, Lee GM, Parkhill J, Bentley SD, Hanage WP, Lipsitch M. Population genomics of post-vaccine changes in pneumococcal epidemiology. Nat Genet. 2013;45(6):656\u201363. \n                    https:\/\/doi.org\/10.1038\/ng.2625\n                    \n                  .","journal-title":"Nat Genet"},{"issue":"3","key":"119_CR38","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1038\/ng.2895","volume":"46","author":"C Chewapreecha","year":"2014","unstructured":"Chewapreecha C, Harris SR, Croucher NJ, Turner C, Marttinen P, Cheng L, Pessia A, Aanensen DM, Mather AE, Page AJ, Salter SJ, Harris D, Nosten F, Goldblatt D, Corander J, Parkhill J, Turner P, Bentley SD. Dense genomic sampling identifies highways of pneumococcal recombination. Nat Genet. 2014;46(3):305\u20139. \n                    https:\/\/doi.org\/10.1038\/ng.2895\n                    \n                  .","journal-title":"Nat Genet"},{"key":"119_CR39","unstructured":"National Center for Biotechnology Information: GeneBank. \n                    ftp:\/\/ftp.ncbi.nih.gov\/genomes\/archive\/old_genbank\/Bacteria\/\n                    \n                  . Accessed 31 Oct 2017."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-017-0119-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T01:00:24Z","timestamp":1589850024000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-017-0119-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,15]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["119"],"URL":"https:\/\/doi.org\/10.1186\/s13015-017-0119-7","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2018,2,15]]},"assertion":[{"value":"31 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}