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

Overview

Journal BMC Genomics

Publisher Biomed Central

Specialty Genetics

Date 2020 Sep 9

PMID 32900378

Citations 11

Authors

Xingyu Yang

Christopher M Tipton

Matthew C Woodruff

Enlu Zhou

F Eun-Hyung Lee

Inaki Sanz

Peng Qiu

Affiliations

Soon will be listed here.

Abstract

Background: 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.

Results: 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. 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.

Conclusions: GLaMST outperforms state-of-art in reconstruction of the BCR lineage tree in both efficiency and accuracy. Integrating it into existing BCR sequencing analysis frameworks can significant improve lineage tree reconstruction aspect of the analysis.

Citing Articles

Isotype-aware inference of B cell clonal lineage trees from single-cell sequencing data.

Weber L, Reiman D, Roddur M, Qi Y, El-Kebir M, Khan A Cell Genom. 2024; 4(9):100637.

PMID: 39208795 PMC: 11480863. DOI: 10.1016/j.xgen.2024.100637.

Protocol for fast clonal family inference and analysis from large-scale B cell receptor repertoire sequencing data.

Wang K, Cai L, Wang H, Shan S, Hu X, Zhang J STAR Protoc. 2024; 5(2):102969.

PMID: 38502687 PMC: 10963638. DOI: 10.1016/j.xpro.2024.102969.

B cell phylogenetics in the single cell era.

Hoehn K, Kleinstein S Trends Immunol. 2023; 45(1):62-74.

PMID: 38151443 PMC: 10872299. DOI: 10.1016/j.it.2023.11.004.

ViCloD, an interactive web tool for visualizing B cell repertoires and analyzing intraclonal diversities: application to human B-cell tumors.

Jeusset L, Abdollahi N, Verny T, Armand M, De Septenville A, Davi F NAR Genom Bioinform. 2023; 5(2):lqad064.

PMID: 37388820 PMC: 10304752. DOI: 10.1093/nargab/lqad064.

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

Abdollahi N, Jeusset L, de Septenville A, Davi F, Bernardes J BMC Bioinformatics. 2023; 24(1):70.

PMID: 36849917 PMC: 9972711. DOI: 10.1186/s12859-022-05112-z.

References

Dunn-Walters D, Belelovsky A, Edelman H, Banerjee M, Mehr R . The dynamics of germinal centre selection as measured by graph-theoretical analysis of mutational lineage trees. Dev Immunol. 2004; 9(4):233-43. PMC: 2276115. DOI: 10.1080/10446670310001593541. View

Whelan S, Lio P, Goldman N . Molecular phylogenetics: state-of-the-art methods for looking into the past. Trends Genet. 2001; 17(5):262-72. DOI: 10.1016/s0168-9525(01)02272-7. View

Tipton C, Fucile C, Darce J, Chida A, Ichikawa T, Gregoretti I . Diversity, cellular origin and autoreactivity of antibody-secreting cell population expansions in acute systemic lupus erythematosus. Nat Immunol. 2015; 16(7):755-65. PMC: 4512288. DOI: 10.1038/ni.3175. View

Yaari G, Kleinstein S . Practical guidelines for B-cell receptor repertoire sequencing analysis. Genome Med. 2015; 7:121. PMC: 4654805. DOI: 10.1186/s13073-015-0243-2. View

Werhli A, Husmeier D . Gene regulatory network reconstruction by Bayesian integration of prior knowledge and/or different experimental conditions. J Bioinform Comput Biol. 2008; 6(3):543-72. DOI: 10.1142/s0219720008003539. View

Calis J, Rosenberg B . Characterizing immune repertoires by high throughput sequencing: strategies and applications. Trends Immunol. 2014; 35(12):581-590. PMC: 4390416. DOI: 10.1016/j.it.2014.09.004. View

Qiu P, Simonds E, Bendall S, Gibbs Jr K, Bruggner R, Linderman M . Extracting a cellular hierarchy from high-dimensional cytometry data with SPADE. Nat Biotechnol. 2011; 29(10):886-91. PMC: 3196363. DOI: 10.1038/nbt.1991. View

Yang Z, Rannala B . Molecular phylogenetics: principles and practice. Nat Rev Genet. 2012; 13(5):303-14. DOI: 10.1038/nrg3186. View

Dunn-Walters D, Edelman H, Mehr R . Immune system learning and memory quantified by graphical analysis of B-lymphocyte phylogenetic trees. Biosystems. 2004; 76(1-3):141-55. DOI: 10.1016/j.biosystems.2004.05.011. View

10.

Gupta N, Vander Heiden J, Uduman M, Gadala-Maria D, Yaari G, Kleinstein S . Change-O: a toolkit for analyzing large-scale B cell immunoglobulin repertoire sequencing data. Bioinformatics. 2015; 31(20):3356-8. PMC: 4793929. DOI: 10.1093/bioinformatics/btv359. View

11.

Barak M, S Zuckerman N, Edelman H, Unger R, Mehr R . IgTree: creating Immunoglobulin variable region gene lineage trees. J Immunol Methods. 2008; 338(1-2):67-74. DOI: 10.1016/j.jim.2008.06.006. View

12.

Georgiou G, Ippolito G, Beausang J, Busse C, Wardemann H, Quake S . The promise and challenge of high-throughput sequencing of the antibody repertoire. Nat Biotechnol. 2014; 32(2):158-68. PMC: 4113560. DOI: 10.1038/nbt.2782. View

13.

Stern J, Yaari G, Vander Heiden J, Church G, Donahue W, Hintzen R . B cells populating the multiple sclerosis brain mature in the draining cervical lymph nodes. Sci Transl Med. 2014; 6(248):248ra107. PMC: 4388137. DOI: 10.1126/scitranslmed.3008879. View

14.

Chor B, Tuller T . Maximum likelihood of evolutionary trees: hardness and approximation. Bioinformatics. 2005; 21 Suppl 1:i97-106. DOI: 10.1093/bioinformatics/bti1027. View

15.

Uduman M, Shlomchik M, Vigneault F, Church G, Kleinstein S . Integrating B cell lineage information into statistical tests for detecting selection in Ig sequences. J Immunol. 2013; 192(3):867-74. PMC: 4363135. DOI: 10.4049/jimmunol.1301551. View

16.

Thompson J, Higgins D, Gibson T . CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res. 1994; 22(22):4673-80. PMC: 308517. DOI: 10.1093/nar/22.22.4673. View

17.

Sok D, Laserson U, Laserson J, Liu Y, Vigneault F, Julien J . The effects of somatic hypermutation on neutralization and binding in the PGT121 family of broadly neutralizing HIV antibodies. PLoS Pathog. 2013; 9(11):e1003754. PMC: 3836729. DOI: 10.1371/journal.ppat.1003754. View

18.

Green M, Gentles A, Nair R, Irish J, Kihira S, Liu C . Hierarchy in somatic mutations arising during genomic evolution and progression of follicular lymphoma. Blood. 2013; 121(9):1604-11. PMC: 3587323. DOI: 10.1182/blood-2012-09-457283. View

19.

He L, Sok D, Azadnia P, Hsueh J, Landais E, Simek M . Toward a more accurate view of human B-cell repertoire by next-generation sequencing, unbiased repertoire capture and single-molecule barcoding. Sci Rep. 2014; 4:6778. PMC: 4894419. DOI: 10.1038/srep06778. View