GLaMST: Grow Lineages along Minimum Spanning Tree for B Cell Receptor Sequencing Data

Abstract

B cell affinity maturation enables B cells to generate high-affinity antibodies. This process involves somatic hypermutation of B cell immunoglobulin receptor (BCR) genes and selection by their ability to bind antigens. Lineage trees are used to describe this microevolution of B cell immunoglobulin genes. In a lineage tree, each node is one BCR sequence that mutated from the germinal center and each directed edge represents a single base mutation, insertion or deletion. In BCR sequencing data, the observed data only contains a subset of BCR sequences in this microevolution process. Therefore, reconstructing the lineage tree from experimental data requires algorithms to build the tree based on partially observed tree nodes. We developed a new algorithm named Grow Lineages along Minimum Spanning Tree (GLaMST), which efficiently reconstruct the lineage tree given observed BCR sequences that correspond to a subset of the tree nodes. GLaMST constructs the minimum-spanning-tree (MST) to approximate the landscape of how observed BCR sequences are related, uses the MST to guide the interpolation of the closest unobserved sequence, updates the MST for the interpolation of additional unobserved sequences, and iterates until a full lineage tree is completed, where all observed sequences are connected by interpolated unobserved sequences and single base operations of mutations, insertions and deletions. Through comparison using simulated and real data, GLaMST outperforms existing algorithms in simulations with high rates of mutation, insertion and deletion, and generates lineage trees with smaller size and closer to ground truth according to tree features that highly correlated with selection pressure.