Reconstructing B cell lineage trees with minimum spanning tree and genotype abundances

Abstract

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.

Keywords: B cell receptor repertoire; Lineage Tree; phylogenetics.

Fig. 1

ClonalTree construction example. We start with a connected weighted graph (a) where nodes represent BCR genotype sequences, edge weights their distances, and node weights their abundances. The graph can be fully connected, or one can disable edges whose weight is lower than a threshold $\delta$. Then, we first place the inferred ancestral sequence (the root) (b) and iteratively add nodes to the tree with the lowest edge weight and highest genotype abundance (c, d); when edges have the same weight (e), we choose that connected to the node with the highest abundance (f), we repeat until all nodes were added to the tree (g), the final tree is shown in (h)

Fig. 2

Performance comparison between GCtree, ClonalTree, and GLaMST using GED distances. Box-plots in a present GED tree-based distances, while b display GED path-based ones

Fig. 3

Most Recent Common Ancestor (MRCA) distance distributions. a compares ClonalTree, and GLaMST with ground truth trees, and b with trees generated by GCtree

Fig. 4

Correctness Of Ancestral Reconstruction (COAR) distance distributions. a compares ClonalTree, and GLaMST with ground truth trees, while b with trees generated by GCtree