{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T04:31:02Z","timestamp":1794544262657,"version":"4.9.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T00:00:00Z","timestamp":1677456000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T00:00:00Z","timestamp":1677456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"2016 Programme Doctoral de Canc\u00e9rologie"},{"name":"SIRIC CURAMUS","award":["S20JRAP016 2020-2021"],"award-info":[{"award-number":["S20JRAP016 2020-2021"]}]},{"name":"SIRIC CURAMUS","award":["S20JRAP016 2020-2021"],"award-info":[{"award-number":["S20JRAP016 2020-2021"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>B cell receptor (BCR) genes exposed to an antigen undergo somatic hypermutations and Darwinian antigen selection, generating a large BCR-antibody diversity. This process, known as B cell affinity maturation, increases antibody affinity, forming a specific B cell lineage that includes the unmutated ancestor and mutated variants. In a B cell lineage, cells with a higher antigen affinity will undergo clonal expansion, while those with a lower affinity will not proliferate and probably be eliminated. Therefore, cellular (genotype) abundance provides a valuable perspective on the ongoing evolutionary process. Phylogenetic tree inference is often used to reconstruct B cell lineage trees and represents the evolutionary dynamic of BCR affinity maturation. However, such methods should process B-cell population data derived from experimental sampling that might contain different cellular abundances. There are a few phylogenetic methods for tracing the evolutionary events occurring in B cell lineages; best-performing solutions are time-demanding and restricted to analysing a reduced number of sequences, while time-efficient methods do not consider cellular abundances. We propose ClonalTree, a low-complexity and accurate approach to construct B-cell lineage trees that incorporates genotype abundances into minimum spanning tree (MST) algorithms. Using both simulated and experimental data, we demonstrate that ClonalTree outperforms MST-based algorithms and achieves a comparable performance to a method that explores tree-generating space exhaustively. Furthermore, ClonalTree has a lower running time, being more convenient for building B-cell lineage trees from high-throughput BCR sequencing data, mainly in biomedical applications, where a lower computational time is appreciable. It is hundreds to thousands of times faster than exhaustive approaches, enabling the analysis of a large set of sequences within minutes or seconds and without loss of accuracy. The source code is freely available at github.com\/julibinho\/ClonalTree.<\/jats:p>","DOI":"10.1186\/s12859-022-05112-z","type":"journal-article","created":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T10:03:32Z","timestamp":1677492212000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Reconstructing B cell lineage trees with minimum spanning tree and genotype abundances"],"prefix":"10.1186","volume":"24","author":[{"given":"Nika","family":"Abdollahi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lucile","family":"Jeusset","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anne","family":"de Septenville","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frederic","family":"Davi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juliana Silva","family":"Bernardes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,2,27]]},"reference":[{"issue":"2","key":"5112_CR1","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0092-8674(02)00675-X","volume":"109","author":"CH Bassing","year":"2002","unstructured":"Bassing CH, Swat W, Alt FW. The mechanism and regulation of chromosomal v (d) j recombination. Cell. 2002;109(2):45\u201355.","journal-title":"Cell"},{"issue":"5909","key":"5112_CR2","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1038\/302575a0","volume":"302","author":"S Tonegawa","year":"1983","unstructured":"Tonegawa S. Somatic generation of antibody diversity. Nature. 1983;302(5909):575\u201381.","journal-title":"Nature"},{"key":"5112_CR3","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1146\/annurev-immunol-020711-075032","volume":"30","author":"GD Victora","year":"2012","unstructured":"Victora GD, Nussenzweig MC. Germinal centers. Annu Rev Immunol. 2012;30:429\u201357.","journal-title":"Annu Rev Immunol"},{"issue":"5","key":"5112_CR4","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1073\/pnas.1617959114","volume":"114","author":"CF de Bourcy","year":"2017","unstructured":"de Bourcy CF, Angel CJL, Vollmers C, Dekker CL, Davis MM, Quake SR. Phylogenetic analysis of the human antibody repertoire reveals quantitative signatures of immune senescence and aging. Proc Natl Acad Sci. 2017;114(5):1105\u201310.","journal-title":"Proc Natl Acad Sci"},{"key":"5112_CR5","doi-asserted-by":"crossref","unstructured":"Safonova Y, Pevzner PA. Igevolution: clonal analysis of antibody repertoires. bioRxiv, 2019;725424","DOI":"10.1101\/725424"},{"key":"5112_CR6","doi-asserted-by":"publisher","first-page":"681","DOI":"10.3389\/fimmu.2016.00681","volume":"7","author":"DW Lee","year":"2017","unstructured":"Lee DW, Khavrutskii IV, Wallqvist A, Bavari S, Cooper CL, Chaudhury S. Brilia: integrated tool for high-throughput annotation and lineage tree assembly of b-cell repertoires. Front Immunol. 2017;7:681.","journal-title":"Front Immunol"},{"issue":"7381","key":"5112_CR7","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1038\/nature10762","volume":"481","author":"M Greaves","year":"2012","unstructured":"Greaves M, Maley CC. Clonal evolution in cancer. Nature. 2012;481(7381):306\u201313.","journal-title":"Nature"},{"issue":"5","key":"5112_CR8","doi-asserted-by":"publisher","first-page":"1147","DOI":"10.1093\/molbev\/msw015","volume":"33","author":"KB Hoehn","year":"2016","unstructured":"Hoehn KB, Fowler A, Lunter G, Pybus OG. The diversity and molecular evolution of b-cell receptors during infection. Mol Biol Evol. 2016;33(5):1147\u201357.","journal-title":"Mol Biol Evol"},{"issue":"Database issue","key":"5112_CR9","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1093\/nar\/gki010","volume":"33","author":"V Giudicelli","year":"2004","unstructured":"Giudicelli V, Chaume D, Lefranc M-P. IMGT\/GENE-DB: a comprehensive database for human and mouse immunoglobulin and T cell receptor genes. Nucleic Acids Res. 2004;33(Database issue):256\u201361.","journal-title":"Nucleic Acids Res"},{"key":"5112_CR10","doi-asserted-by":"crossref","unstructured":"Alamyar E, Duroux P, Lefranc M-P, Giudicelli V. Imgt\u00ae tools for the nucleotide analysis of immunoglobulin (ig) and t cell receptor (tr) v-(d)-j repertoires, polymorphisms, and ig mutations: Imgt\/v-quest and imgt\/highv-quest for ngs. In: Immunogenetics. Springer, p. 569\u2013604 (2012)","DOI":"10.1007\/978-1-61779-842-9_32"},{"issue":"6277","key":"5112_CR11","doi-asserted-by":"publisher","first-page":"1048","DOI":"10.1126\/science.aad3439","volume":"351","author":"JM Tas","year":"2016","unstructured":"Tas JM, Mesin L, Pasqual G, Targ S, Jacobsen JT, Mano YM, Chen CS, Weill J-C, Reynaud C-A, Browne EP. Visualizing antibody affinity maturation in germinal centers. Science. 2016;351(6277):1048\u201354.","journal-title":"Science"},{"issue":"3","key":"5112_CR12","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.immuni.2016.02.010","volume":"44","author":"M Kuraoka","year":"2016","unstructured":"Kuraoka M, Schmidt AG, Nojima T, Feng F, Watanabe A, Kitamura D, Harrison SC, Kepler TB, Kelsoe G. Complex antigens drive permissive clonal selection in germinal centers. Immunity. 2016;44(3):542\u201352.","journal-title":"Immunity"},{"key":"5112_CR13","doi-asserted-by":"publisher","first-page":"2451","DOI":"10.3389\/fimmu.2018.02451","volume":"9","author":"K Davidsen","year":"2018","unstructured":"Davidsen K, Matsen FA IV. Benchmarking tree and ancestral sequence inference for b cell receptor sequences. Front Immunol. 2018;9:2451.","journal-title":"Front Immunol"},{"issue":"24","key":"5112_CR14","doi-asserted-by":"publisher","first-page":"3938","DOI":"10.1093\/bioinformatics\/btx533","volume":"33","author":"A Yermanos","year":"2017","unstructured":"Yermanos A, Greiff V, Krautler NJ, Menzel U, Dounas A, Miho E, Oxenius A, Stadler T, Reddy ST. Comparison of methods for phylogenetic b-cell lineage inference using time-resolved antibody repertoire simulations (absim). Bioinformatics. 2017;33(24):3938\u201346.","journal-title":"Bioinformatics"},{"issue":"1\u20132","key":"5112_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.jim.2008.06.006","volume":"338","author":"M Barak","year":"2008","unstructured":"Barak M, Zuckerman NS, Edelman H, Unger R, Mehr R. Igtree: creating immunoglobulin variable region gene lineage trees. J Immunol Methods. 2008;338(1\u20132):67\u201374.","journal-title":"J Immunol Methods"},{"issue":"6","key":"5112_CR16","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/BF01734359","volume":"17","author":"J Felsenstein","year":"1981","unstructured":"Felsenstein J. Evolutionary trees from dna sequences: a maximum likelihood approach. J Mol Evol. 1981;17(6):368\u201376.","journal-title":"J Mol Evol"},{"issue":"12","key":"5112_CR17","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.1101\/gr.8.12.1233","volume":"8","author":"P Li\u00f2","year":"1998","unstructured":"Li\u00f2 P, Goldman N. Models of molecular evolution and phylogeny. Genome Res. 1998;8(12):1233\u201344.","journal-title":"Genome Res"},{"issue":"1","key":"5112_CR18","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1534\/genetics.116.196303","volume":"206","author":"KB Hoehn","year":"2017","unstructured":"Hoehn KB, Lunter G, Pybus OG. A phylogenetic codon substitution model for antibody lineages. Genetics. 2017;206(1):417\u201327.","journal-title":"Genetics"},{"issue":"5","key":"5112_CR19","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1093\/molbev\/msy020","volume":"35","author":"WS DeWitt III","year":"2018","unstructured":"DeWitt WS III, Mesin L, Victora GD, Minin VN, Matsen FA IV. Using genotype abundance to improve phylogenetic inference. Mol Biol Evol. 2018;35(5):1253\u201365.","journal-title":"Mol Biol Evol"},{"key":"5112_CR20","unstructured":"Felsenstein J. PHYLIP (phylogeny Inference Package), Version 3.5 C. Joseph Felsenstein (1993)"},{"key":"5112_CR21","doi-asserted-by":"crossref","unstructured":"Harris TE. The theory of branching process (1964)","DOI":"10.1007\/978-3-642-51866-9"},{"issue":"9","key":"5112_CR22","first-page":"1","volume":"21","author":"X Yang","year":"2020","unstructured":"Yang X, Tipton CM, Woodruff MC, Zhou E, Lee FE-H, Sanz I, Qiu P. Glamst: Grow lineages along minimum spanning tree for b cell receptor sequencing data. BMC Genomics. 2020;21(9):1\u201311.","journal-title":"BMC Genomics"},{"issue":"3","key":"5112_CR23","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/TSMC.1983.6313167","volume":"SMC\u201313","author":"A Sanfeliu","year":"1983","unstructured":"Sanfeliu A, Sanfeliu A, Fu KS. A distance measure between attributed relational graphs for pattern recognition. IEEE Trans Syst Man Cybern. 1983;SMC\u201313(3):353\u201362.","journal-title":"IEEE Trans Syst Man Cybern"},{"key":"5112_CR24","doi-asserted-by":"crossref","unstructured":"Lefranc M-P, Duroux P, Li S, Giudicelli V, Alamyar E. IMGT\/highv-quest: the IMGT web portal for immunoglobulin (ig) or antibody and t cell receptor (tr) analysis from ngs high throughput and deep sequencing. Immunome Res 2012;08(01).","DOI":"10.4172\/1745-7580.1000056"},{"key":"5112_CR25","doi-asserted-by":"crossref","unstructured":"Sievers F, Higgins DG. Clustal omega, accurate alignment of very large numbers of sequences. In: Multiple Sequence Alignment Methods. Springer, p. 105\u2013116 (2014)","DOI":"10.1007\/978-1-62703-646-7_6"},{"issue":"6","key":"5112_CR26","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R Prim","year":"1957","unstructured":"Prim R. Shortest connection networks and some generalizations. Bell Syst Tech J. 1957;36(6):1389\u2013401.","journal-title":"Bell Syst Tech J"},{"issue":"1","key":"5112_CR27","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.","journal-title":"Proc Am Math Soc"},{"issue":"6","key":"5112_CR28","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00158-003-0368-6","volume":"26","author":"RT Marler","year":"2004","unstructured":"Marler RT, Arora JS. Survey of multi-objective optimization methods for engineering. Struct Multidiscipl Optim. 2004;26(6):369\u201395.","journal-title":"Struct Multidiscipl Optim"},{"issue":"2","key":"5112_CR29","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1109\/TAC.1967.1098537","volume":"12","author":"F Waltz","year":"1967","unstructured":"Waltz F. An engineering approach: hierarchical optimization criteria. IEEE Trans Autom Control. 1967;12(2):179\u201380.","journal-title":"IEEE Trans Autom Control"},{"key":"5112_CR30","doi-asserted-by":"crossref","unstructured":"Huang F, Gao P, Wang Y. Comparison of prim and Kruskal on shanghai and Shenzhen 300 index hierarchical structure tree. In: 2009 International Conference on Web Information Systems and Mining (2009). p. 237\u2013241.","DOI":"10.1109\/WISM.2009.56"},{"key":"5112_CR31","unstructured":"Fredman ML. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. Technical Report\u00a03."},{"key":"5112_CR32","first-page":"707","volume":"10","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein VI. Binary codes capable of correcting deletions, insertions, and reversals. Sov Phys Doklady. 1966;10:707\u201310.","journal-title":"Sov Phys Doklady"},{"issue":"2","key":"5112_CR33","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/j.1538-7305.1950.tb00463.x","volume":"29","author":"RW Hamming","year":"1950","unstructured":"Hamming RW. Error detecting and error correcting codes. Bell Syst Tech J. 1950;29(2):147\u201360.","journal-title":"Bell Syst Tech J"},{"key":"5112_CR34","doi-asserted-by":"publisher","first-page":"358","DOI":"10.3389\/fimmu.2013.00358","volume":"4","author":"G Yaari","year":"2013","unstructured":"Yaari G, Vander Heiden J, Uduman M, Gadala-Maria D, Gupta N, Stern JN, O\u2019Connor K, Hafler D, Laserson U, Vigneault F. Models of somatic hypermutation targeting and substitution based on synonymous mutations from high-throughput immunoglobulin sequencing data. Front Immunol. 2013;4:358.","journal-title":"Front Immunol"},{"issue":"10","key":"5112_CR35","doi-asserted-by":"publisher","first-page":"1005086","DOI":"10.1371\/journal.pcbi.1005086","volume":"12","author":"DK Ralph","year":"2016","unstructured":"Ralph DK, Matsen FA IV. Likelihood-based inference of b cell clonal families. PLoS Comput Biol. 2016;12(10):1005086.","journal-title":"PLoS Comput Biol"},{"key":"5112_CR36","unstructured":"Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. Mathematical Sciences Series. W.H. Freeman (1979)"},{"key":"5112_CR37","volume-title":"Bridging the gap between graph edit distance and kernel machines. Series in machine perception and artificial intelligence","author":"M Neuhaus","year":"2007","unstructured":"Neuhaus M, Bunke H. Bridging the gap between graph edit distance and kernel machines. Series in machine perception and artificial intelligence. Singapore: World Scientific; 2007."},{"key":"5112_CR38","doi-asserted-by":"crossref","unstructured":"Riesen K. Structural pattern recognition with graph edit distance: approximation algorithms and applications. Advances in Computer Vision and Pattern Recognition. Springer (2016)","DOI":"10.1007\/978-3-319-27252-8"},{"issue":"3","key":"5112_CR39","doi-asserted-by":"publisher","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"},{"key":"5112_CR40","doi-asserted-by":"crossref","unstructured":"Kepler TB. Reconstructing a b-cell clonal lineage. i. statistical inference of unobserved ancestors. F1000Research 2013;2.","DOI":"10.12688\/f1000research.2-103.v1"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-022-05112-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-022-05112-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-022-05112-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T10:03:49Z","timestamp":1677492229000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-022-05112-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,27]]},"references-count":40,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["5112"],"URL":"https:\/\/doi.org\/10.1186\/s12859-022-05112-z","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2134434\/v1","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,27]]},"assertion":[{"value":"5 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Informed consent for use of the patients samples for research purposes was obtained.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"70"}}