24 May 2017 in IEEE/ACM Transactions on Computational Biology and Bioinformatics
Background: Microbial communities from environmental samples show great diversity as bacteria quickly responds to changes in their ecosystems. To assess the scenario of the actual changes, metagenomics experiments aimed at sequencing genomic DNA from such samples are performed. These new obtained sequences together with already known are used to infer phylogenetic trees assessing the taxonomic groups the species with these genes belong to. Here, we propose the first approach to the gene-species assignment problem by using reconciliation with horizontal gene transfer. Results: We propose efficient algorithms that search for optimal gene-species mappings taking into account gene duplication, loss and transfer events under two tractable models of HGT reconciliation. Conclusions: We calculate both the optimal cost and all possible optimal scenarios. Furthermore as the number of optimal reconstructions can be large, we use a Monte-Carlo method for the inference of approximate distributions of gene-species assignments. We demonstrate the applicability on empirical and simulated datasets.
19 May 2022 in Algorithms for Molecular Biology
Background: Phylogenetic networks are mathematical models of evolutionary processes involving reticulate events such as hybridization, recombination, or horizontal gene transfer. One of the crucial notions in phylogenetic network modelling is displayed tree, which is obtained from a network by removing a set of reticulation edges. Displayed trees may represent an evolutionary history of a gene family if the evolution is shaped by reticulation events. Results: We address the problem of inferring an optimal tree displayed by a network, given a gene tree G and a tree-child network N, under the deep coalescence and duplication costs. We propose an O(mn)-time dynamic programming algorithm (DP) to compute a lower bound of the optimal displayed tree cost, where m and n are the sizes of G and N, respectively. In addition, our algorithm can verify whether the solution is exact. Moreover, it provides a set of reticulation edges corresponding to the obtained cost. If the cost is exact, the set induces an optimal displayed tree. Otherwise, the set contains pairs of conflicting edges, i.e., edges sharing a reticulation node. Next, we show a conflict resolution algorithm that requires $$2^{r+1}-1$$ invocations of DP in the worst case, where r is the number of reticulations. We propose a similar $$O(2^kmn)$$ -time algorithm for level-k tree-child networks and a branch and bound solution to compute lower and upper bounds of optimal costs. We also extend the algorithms to a broader class of phylogenetic networks. Based on simulated data, the average runtime is $$\Theta (2^{{0.543}k}mn)$$ under the deep-coalescence cost and $$\Theta (2^{{0.355}k}mn)$$ under the duplication cost. Conclusions: Despite exponential complexity in the worst case, our algorithms perform significantly well on empirical and simulated datasets, due to the strategy of resolving internal dissimilarities between gene trees and networks. Therefore, the algorithms are efficient alternatives to enumeration strategies commonly proposed in the literature and enable analyses of complex networks with dozens of reticulations.
1 January 2018 in IEEE/ACM Transactions on Computational Biology and Bioinformatics
Based on the classical non-parametric bootstrapping for phylogenetic trees, we propose a novel bootstrap method to define support for gene duplication and speciation events. By comparing bootstrap gene trees to the original gene tree, we calculate support for evolutionary events. While this approach can be used to annotate orthology and paralogy, we show how it can be used to verify the reliability of tree reconciliation. We propose a linear time algorithm for the computation of bootstrap values, and we show the correspondence of our method with the classical non-parametric bootstrapping. Finally, we present two computational experiments. In the first one, based on simulated data and nine yeast genomes, we show a comparative study of several tree rooting methods and evaluation of their performance by using our bootstrapping method. In the second experiment, using data from the TreeFam database, we tested how the reliability of the gene trees influence the inferred supertree. We found out that species trees inferred from gene trees having highly supported events are more biologically consistent.
13 November 2019 in Blood
Objectives: Follicular lymphoma (FL) typically originates from premalignant mature B cells that carry the founder t(14;18) BCL2 translocation. Mutations in epigenetic modifiers and acquisition of N-glycosylation sites in CDR regions of the B-cell receptor (BCR) are recurrent secondary events in FL pathogenesis. Despite these oncogenic drivers, FL can remain indolent and clinically stable for years. The molecular events driving subclonal evolution into symptomatic progression and eventual transformation to aggressive lymphoma are insufficiently understood. FL cells are frozen in their B-cell development at the germinal center stage and undergo continuous somatic hypermutation mediated by expression of activation-induced deaminase (AID). We aim to identify crucial drivers of subclonal FL evolution by high-throughput mapping at single-cell resolution. Methods: Viable FL cells were isolated and cryopreserved from 23 histologically or immunocytologically confirmed FL samples from 13 patients with informed consent. Full-length VDJ/VJ transcripts were isolated by unbiased template-switching ARTISAN PCR and massive parallel NGS sequencing on the PacBio platform. The clonal primordial FL BCR (pBCR) was reconstructed from unmutated IGV/IGJ sequences with the CDR3 of the least mutated BCR. Since the IgTree program was unable to process the obtained numbers of BCR sequences, we developed the WILLOW algorithm for analysis of BCR evolution based on the principle of maximum parsimony and on distance from the pBCR. Intraclonal BCR variability was quantified by Shannon's diversity index. 5' single cell transcriptomics and VDJ/VJ sequencing was performed on 2 pools of highly purified FL cells from 5 lymph node biopsies on the 10x Genomics platform. Data were deconvoluted based on expressed variants by the Single Cell Sample Matcher (SCSM) algorithm. Clustering based on gene expression profiles was performed by shared nearest neighbour (SNN) modularity optimization within the R Seurat package. Genes whose expression differed significantly (adjusted p<0.05) between clusters were assigned to gene ontology terms. Results: ARTISAN PCR/PacBio NGS yielded a median of 743 full-length VDJ and VJ sequences (range 62-12782) per BCR chain with expected high intraclonal diversity (median 200 subclones, range 15-3301). WILLOW revealed dominant FL subclones with a subclonal hierarchy wherein multiple routes converged to offspring nodes with identical additional mutations rather than tree-like branching (Figure). In serial samples of 4 patients, lymph node biopsies had only marginally higher subclonal diversity than blood or bone marrow samples (p=0,055; Wilcoxon's matched-pairs signed rank test). Overall BCR mutational burden increased over time in sequential biopsies. Two cases of histological FL transformation were dominated by a single subclone (65% and 80% of all VDJ/VJ sequences, respectively) that was rare in the preceding FL BCR network (0.2% and 1.8%). Pooled transcriptomics data from 6050-6500 cells were assigned to individual samples by SCSM and revealed up to seven transcriptional clusters per FL. In 9 of 10 FL, genes assigned to immune function strongly contributed to separation into one or more clusters. Single cell VDJ/VJ sequencing yielded combined heavy and light chain BCR sequences for a median of 502 FL cells per biopsy (range 22 - 1919) that permitted mapping of subclonal evolution by WILLOW based on complete BCR information. Transcriptome clusters were not distributed evenly throughout the WILLOW FL BCR networks but rather statistically associated with distinct major FL subclones. Vice versa, major FL subclones within the same biopsy were distinguished by particular gene expression profiles. Conclusions: WILLOW facilitates mapping of subclonal FL evolution based on high-throughput BCR sequencing. FL evolution proceeds in networks rather than tree-like branching, whereby acquisition of certain combinations of several BCR mutations can occur in parallel in different trajectories. Transcriptomic profiling of single FL cells identifies distinct clusters within a single biopsy. Mapping of these clusters to the FL cell position in the subclonal FL evolutionary network identifies putative mechanisms that are associated with subclonal progression. These mechanisms involve physiological B-cell signalling pathways. Figure Disclosures: No relevant conflicts of interest to declare.