{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T06:17:09Z","timestamp":1772173029397,"version":"3.50.1"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1010303","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000}}],"reference-count":56,"publisher":"Public Library of Science (PLoS)","issue":"8","license":[{"start":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T00:00:00Z","timestamp":1659916800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"VW Foundation","award":["VWZN3157"],"award-info":[{"award-number":["VWZN3157"]}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>\n                    Most methods for phylogenetic tree reconstruction are based on sequence alignments; they infer phylogenies from substitutions that may have occurred at the aligned sequence positions. Gaps in alignments are usually not employed as phylogenetic signal. In this paper, we explore an alignment-free approach that uses insertions and deletions (indels) as an additional source of information for phylogeny inference. For a set of four or more input sequences, we generate so-called\n                    <jats:italic>quartet blocks<\/jats:italic>\n                    of four putative homologous segments each. For\n                    <jats:italic>pairs<\/jats:italic>\n                    of such quartet blocks involving the same four sequences, we compare the distances between the two blocks in these sequences, to obtain hints about indels that may have happened between the blocks since the respective four sequences have evolved from their last common ancestor. A prototype implementation that we call\n                    <jats:italic>Gap-SpaM<\/jats:italic>\n                    is presented to infer phylogenetic trees from these data, using a\n                    <jats:italic>quartet-tree<\/jats:italic>\n                    approach or, alternatively, under the\n                    <jats:italic>maximum-parsimony<\/jats:italic>\n                    paradigm. This approach should not be regarded as an alternative to established methods, but rather as a complementary source of phylogenetic information. Interestingly, however, our software is able to produce phylogenetic trees from putative indels alone that are comparable to trees obtained with existing alignment-free methods.\n                  <\/jats:p>","DOI":"10.1371\/journal.pcbi.1010303","type":"journal-article","created":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T13:35:41Z","timestamp":1659965741000},"page":"e1010303","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":6,"title":["Insertions and deletions as phylogenetic signal in an alignment-free context"],"prefix":"10.1371","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6946-5613","authenticated-orcid":true,"given":"Niklas","family":"Birth","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Dencker","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7431-2862","authenticated-orcid":true,"given":"Burkhard","family":"Morgenstern","sequence":"additional","affiliation":[]}],"member":"340","published-online":{"date-parts":[[2022,8,8]]},"reference":[{"key":"pcbi.1010303.ref001","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1093\/bioinformatics\/btu033","article-title":"RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies","volume":"30","author":"A Stamatakis","year":"2014","journal-title":"Bioinformatics"},{"key":"pcbi.1010303.ref002","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1093\/sysbio\/syq010","article-title":"New algorithms and methods to estimate maximum-likelihood phylogenies: assessing the performance of PhyML 3.0","volume":"59","author":"S Guindon","year":"2010","journal-title":"Syst Biol"},{"key":"pcbi.1010303.ref003","doi-asserted-by":"crossref","first-page":"1572","DOI":"10.1093\/bioinformatics\/btg180","article-title":"MrBayes 3: Bayesian phylogenetic inference under mixed models","volume":"19","author":"F Ronquist","year":"2003","journal-title":"Bioinformatics"},{"key":"pcbi.1010303.ref004","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1093\/sysbio\/19.1.83","article-title":"Methods for Computing Wagner Trees","volume":"19","author":"JS Farris","year":"1970","journal-title":"Systematic Biology"},{"key":"pcbi.1010303.ref005","doi-asserted-by":"crossref","first-page":"406","DOI":"10.2307\/2412116","article-title":"Toward defining the course of evolution: minimum change for a specific tree topology","volume":"20","author":"W Fitch","year":"1971","journal-title":"Systematic Zoology"},{"key":"pcbi.1010303.ref006","unstructured":"Swofford D. PAUP*. Phylogenetic Analysis Using Parsimony (*and Other Methods). Version 4.0b10. Sinauer Associates, Sunderland, Massachusetts. 2003;."},{"key":"pcbi.1010303.ref007","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.tree.2004.03.015","article-title":"The evolution of supertrees","volume":"19","author":"ORP Bininda-Emonds","year":"2004","journal-title":"Trends in Ecology and Evolution"},{"issue":"Suppl 6","key":"pcbi.1010303.ref008","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1186\/s12859-018-2129-y","article-title":"ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees","volume":"19","author":"C Zhang","year":"2018","journal-title":"BMC Bioinformatics"},{"key":"pcbi.1010303.ref009","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/1055-7903(92)90035-F","article-title":"Phylogenetic inference based on matrix representation of trees","volume":"1","author":"MA Ragan","year":"1992","journal-title":"Mol Phylogenet Evol"},{"key":"pcbi.1010303.ref010","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/BF02193625","article-title":"An evolutionary model for maximum likelihood alignment of DNA sequences","volume":"33","author":"JL Thorne","year":"1991","journal-title":"J Mol Evol"},{"key":"pcbi.1010303.ref011","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF00163848","article-title":"Inching toward reality: An improved likelihood model of sequence evolution","volume":"34","author":"JL Thorne","year":"1992","journal-title":"Journal of Molecular Evolution"},{"key":"pcbi.1010303.ref012","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1186\/s12859-017-1665-1","article-title":"Solving the master equation for Indels","volume":"18","author":"IH Holmes","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"pcbi.1010303.ref013","doi-asserted-by":"crossref","first-page":"772","DOI":"10.1080\/10635150802434394","article-title":"Wagner and Dollo: a stochastic duet by composing two parsimonious solos","volume":"57","author":"AV Alekseyenko","year":"2008","journal-title":"Systematic Biology"},{"key":"pcbi.1010303.ref014","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1093\/molbev\/msh043","article-title":"A \u201cLong Indel\u201d Model For Evolutionary Sequence Alignment","volume":"21","author":"I Mikl\u00f3s","year":"2004","journal-title":"Molecular Biology and Evolution"},{"key":"pcbi.1010303.ref015","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1093\/sysbio\/49.2.369","article-title":"Gaps as characters in sequence-based phylogenetic analyses","volume":"49","author":"MP Simmons","year":"2000","journal-title":"Syst Biol"},{"issue":"3","key":"pcbi.1010303.ref016","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1016\/j.ympev.2005.07.011","article-title":"Incorporating information from length-mutational events into phylogenetic analysis","volume":"38","author":"K M\u00fcller","year":"2006","journal-title":"Mol Phylogenet Evol"},{"key":"pcbi.1010303.ref017","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1016\/j.ympev.2006.07.021","article-title":"How should gaps be treated in parsimony? A comparison of approaches using simulation","volume":"42","author":"TH Ogden","year":"2007","journal-title":"Mol Phylogenet Evol"},{"key":"pcbi.1010303.ref018","doi-asserted-by":"crossref","DOI":"10.3390\/d11070108","article-title":"Phylogenetic Signal of Indels and the Neoavian Radiation","volume":"11","author":"P Houde","year":"2019","journal-title":"Diversity"},{"key":"pcbi.1010303.ref019","doi-asserted-by":"crossref","first-page":"R37","DOI":"10.1186\/gb-2010-11-4-r37","article-title":"Phylogenetic assessment of alignments reveals neglected tree signal in gaps","volume":"11","author":"C Dessimoz","year":"2010","journal-title":"Genome Biol"},{"key":"pcbi.1010303.ref020","doi-asserted-by":"crossref","first-page":"2677","DOI":"10.1073\/pnas.0813249106","article-title":"Alignment-free genome comparison with feature frequency profiles (FFP) and optimal resolutions","volume":"106","author":"GE Sims","year":"2009","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"suppl 2","key":"pcbi.1010303.ref021","doi-asserted-by":"crossref","first-page":"W45","DOI":"10.1093\/nar\/gkh362","article-title":"CVTree: a phylogenetic tree reconstruction tool based on whole genomes","volume":"32","author":"J Qi","year":"2004","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010303.ref022","doi-asserted-by":"crossref","first-page":"1991","DOI":"10.1093\/bioinformatics\/btu177","article-title":"Fast Alignment-Free sequence comparison using spaced-word frequencies","volume":"30","author":"CA Leimeister","year":"2014","journal-title":"Bioinformatics"},{"key":"pcbi.1010303.ref023","doi-asserted-by":"crossref","first-page":"13980","DOI":"10.1073\/pnas.202468099","article-title":"Distributional regimes for the number of k-word matches between two random sequences","volume":"99","author":"RA Lippert","year":"2002","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"pcbi.1010303.ref024","doi-asserted-by":"crossref","first-page":"2000","DOI":"10.1093\/bioinformatics\/btu331","article-title":"kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison","volume":"30","author":"CA Leimeister","year":"2014","journal-title":"Bioinformatics"},{"key":"pcbi.1010303.ref025","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1089\/cmb.2006.13.336","article-title":"The average common substring approach to phylogenomic reconstruction","volume":"13","author":"I Ulitsky","year":"2006","journal-title":"Journal of Computational Biology"},{"key":"pcbi.1010303.ref026","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1186\/s13015-017-0118-8","article-title":"Phylogeny reconstruction based on the length distribution of k-mismatch common substrings","volume":"12","author":"B Morgenstern","year":"2017","journal-title":"Algorithms for Molecular Biology"},{"key":"pcbi.1010303.ref027","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"N Saitou","year":"1987","journal-title":"Molecular Biology and Evolution"},{"key":"pcbi.1010303.ref028","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1093\/oxfordjournals.molbev.a025808","article-title":"BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data","volume":"14","author":"O Gascuel","year":"1997","journal-title":"Molecular Biology and Evolution"},{"key":"pcbi.1010303.ref029","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1093\/bioinformatics\/btg005","article-title":"Alignment-free sequence comparison\u2014a review","volume":"19","author":"S Vinga","year":"2003","journal-title":"Bioinformatics"},{"key":"pcbi.1010303.ref030","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1093\/bib\/bbt083","article-title":"Alignment-free phylogenetics and population genetics","volume":"15","author":"B Haubold","year":"2014","journal-title":"Briefings in Bioinformatics"},{"key":"pcbi.1010303.ref031","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1093\/bib\/bbx067","article-title":"Alignment-free inference of hierarchical and reticulate phylogenomic relationships","volume":"22","author":"G Bernard","year":"2019","journal-title":"Briefings in Bioinformatics"},{"key":"pcbi.1010303.ref032","doi-asserted-by":"crossref","first-page":"e75","DOI":"10.1093\/nar\/gkt003","article-title":"Co-phylog: an assembly-free phylogenomic approach for closely related organisms","volume":"41","author":"H Yi","year":"2013","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010303.ref033","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1093\/bioinformatics\/btu815","article-title":"andi: Fast and accurate estimation of evolutionary distances between closely related genomes","volume":"31","author":"B Haubold","year":"2015","journal-title":"Bioinformatics"},{"key":"pcbi.1010303.ref034","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1093\/bioinformatics\/btw776","article-title":"Fast and Accurate Phylogeny Reconstruction using Filtered Spaced-Word Matches","volume":"33","author":"CA Leimeister","year":"2017","journal-title":"Bioinformatics"},{"key":"pcbi.1010303.ref035","doi-asserted-by":"crossref","first-page":"W7","DOI":"10.1093\/nar\/gku398","article-title":"Spaced words and kmacs: fast alignment-free sequence comparison based on inexact word matches","volume":"42","author":"S Horwege","year":"2014","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010303.ref036","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1186\/s13015-015-0032-x","article-title":"Estimating evolutionary distances between genomic sequences from spaced-word matches","volume":"10","author":"B Morgenstern","year":"2015","journal-title":"Algorithms for Molecular Biology"},{"key":"pcbi.1010303.ref037","doi-asserted-by":"crossref","first-page":"giy148","DOI":"10.1093\/gigascience\/giy148","article-title":"Prot-SpaM: Fast alignment-free phylogeny reconstruction based on whole-proteome sequences","volume":"8","author":"CA Leimeister","year":"2019","journal-title":"GigaScience"},{"key":"pcbi.1010303.ref038","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1186\/s12859-019-3205-7","article-title":"Read-SpaM: assembly-free and alignment-free comparison of bacterial genomes with low sequencing coverage","volume":"20","author":"AK Lau","year":"2019","journal-title":"BMC Bioinformatics"},{"key":"pcbi.1010303.ref039","doi-asserted-by":"crossref","first-page":"e0228070","DOI":"10.1371\/journal.pone.0228070","article-title":"The number of k-mer matches between two DNA sequences as a function of k and applications to estimate phylogenetic distances","volume":"15","author":"S R\u00f6hling","year":"2020","journal-title":"PLOS ONE"},{"key":"pcbi.1010303.ref040","first-page":"121","volume-title":"Multiple Sequence Alignment. Methods in Molecular Biology","author":"B Morgenstern","year":"2020"},{"key":"pcbi.1010303.ref041","doi-asserted-by":"crossref","first-page":"lqz013","DOI":"10.1093\/nargab\/lqz013","article-title":"Multi-SpaM: a Maximum-Likelihood approach to phylogeny reconstruction using multiple spaced-word matches and quartet trees","volume":"2","author":"T Dencker","year":"2020","journal-title":"NAR Genomics and Bioinformatics"},{"key":"pcbi.1010303.ref042","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ympev.2011.06.021","article-title":"Quartet MaxCut: A fast algorithm for amalgamating quartet trees","volume":"62","author":"S Snir","year":"2012","journal-title":"Molecular Phylogenetics and Evolution"},{"key":"pcbi.1010303.ref043","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"},{"key":"pcbi.1010303.ref044","unstructured":"Chiaromonte F, Yap VB, Miller W. Scoring Pairwise Genomic Sequence Alignments. In: Altman RB, Dunker AK, Hunter L, Klein TE, editors. Pacific Symposium on Biocomputing. Lihue, Hawaii; 2002. p. 115\u2013126."},{"key":"pcbi.1010303.ref045","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1109\/TCBB.2008.133","article-title":"Quartets MaxCut: A Divide and Conquer Quartets Algorithm","volume":"7","author":"S Snir","year":"2010","journal-title":"IEEE\/ACM Trans Comput Biology Bioinform"},{"key":"pcbi.1010303.ref046","first-page":"164","article-title":"PHYLIP\u2014Phylogeny Inference Package (Version 3.2)","volume":"5","author":"J Felsenstein","year":"1989","journal-title":"Cladistics"},{"key":"pcbi.1010303.ref047","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1186\/s13059-019-1755-7","article-title":"Benchmarking of alignment-free sequence comparison methods","volume":"20","author":"A Zielezinski","year":"2019","journal-title":"Genome Biology"},{"key":"pcbi.1010303.ref048","doi-asserted-by":"crossref","first-page":"16241","DOI":"10.1038\/nmicrobiol.2016.241","article-title":"Comparative genomics provides a timeframe for Wolbachia evolution and exposes a recent biotin synthesis operon transfer","volume":"2","author":"M Gerth","year":"2017","journal-title":"Nature Microbiology"},{"key":"pcbi.1010303.ref049","doi-asserted-by":"crossref","first-page":"e0165702","DOI":"10.1371\/journal.pone.0165702","article-title":"Mitochondrial Genome Sequences and Structures Aid in the Resolution of Piroplasmida phylogeny","volume":"11","author":"ME Schreeg","year":"2016","journal-title":"PLOS ONE"},{"key":"pcbi.1010303.ref050","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.ympev.2012.05.034","article-title":"A mitochondrial genome phylogeny of termites (Blattodea: Termitoidae): Robust support for interfamilial relationships and molecular synapomorphies define major clades","volume":"65","author":"SL Cameron","year":"2012","journal-title":"Molecular Phylogenetics and Evolution"},{"key":"pcbi.1010303.ref051","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","article-title":"Comparison of phylogenetic trees","volume":"53","author":"DF Robinson","year":"1981","journal-title":"Mathematical Biosciences"},{"key":"pcbi.1010303.ref052","unstructured":"Lutteropp S. Quartet Check; 2021. https:\/\/github.com\/lutteropp\/quartet_check."},{"key":"pcbi.1010303.ref053","unstructured":"Birth N. Single Quartet Check; 2021. https:\/\/github.com\/njbirth\/single_quartet_check."},{"key":"pcbi.1010303.ref054","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/s00239-018-9833-0","article-title":"The Performance of Two Supertree Schemes Compared Using Synthetic and Real Data Quartet Input","volume":"86","author":"E Avni","year":"2018","journal-title":"J Mol Evol"},{"key":"pcbi.1010303.ref055","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/1748-7188-6-7","article-title":"An experimental study of Quartets MaxCut and other supertree methods","volume":"6","author":"MS Swenson","year":"2011","journal-title":"Algorithms Mol Biol"},{"key":"pcbi.1010303.ref056","first-page":"407","volume-title":"Molecular Systematics","author":"DL Swofford","year":"1990"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1010303","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,13]],"date-time":"2023-02-13T19:28:47Z","timestamp":1676316527000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010303"}},"subtitle":[],"editor":[{"given":"Jinyan","family":"Li","sequence":"first","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,8,8]]},"references-count":56,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2022,8,8]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1010303","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2021.02.03.429685","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,8]]}}}