HMM architecture.

We follow previous work [25–27] by representing each germline base in each V, D, and J allele as an HMM state (Fig 10). N-additions are represented as a separate class of states, and 5’ (3’) exonuclease deletions as transitions to or from germline states which are not at the start (end) of the gene. All of these states can be combined to create a single HMM for the entire VDJ rearrangement process. While it can be useful to think of individually calculating the probability of each such path, in practice one traverses the dynamic programming (DP) table using the recursion relations found in [23].

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 10. A few states in the internal region of a B cell receptor sequence HMM.

On the left is a state representing a position in a gene with a germline G, which usually emits a G, but sometimes emits other bases (i.e. mutates). If this state is near enough to the start or end of the gene, there will likely be transitions from the initial state, or to the end state (upper arrows). On the other hand, if it is in the middle of a gene the path is more likely to simply traverse the states in order (straight horizontal arrows).

https://doi.org/10.1371/journal.pcbi.1004409.g010

Factorization.

All inferential operations on the HMM described in the previous section can be made faster by a process of “factorization”, which performs inference on a collection of smaller HMMs but returns exactly the same results as a monolithic HMM. Each of these smaller HMMs has the topology obtained by extracting it from the monolithic HMM, resulting in the topologies shown in Fig 11. In order to motivate the procedure, we observe that 1) once a path hits a state corresponding to a given allele, it cannot transition to any state corresponding to a different allele for that segment (for example, a path in allele D₁ cannot transition to D₂); and 2) the only external information needed to calculate the DP table on a single allele’s HMM for a given query sequence is where in the query sequence to start and where to end.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 11. Overall topology of the HMMs in the V, D, and J segments.

Inserts are shown as a single state for clarity, but are replaced by four states in the actual HMM (Fig 12). Note that we include 5’ V and 3’ D exonuclease deletions as a convenience (dashed lines) to account for varying read lengths.

https://doi.org/10.1371/journal.pcbi.1004409.g011

In order to describe the factorization process in more detail, we will use the notation of [23] referring to a single HMM: e_s(b) represents the probability of emitting b in state s, and a_ss′ is the transition probability from state s to s′. We also use π for a path through the set of hidden states, and p_i(x, π) as an abbreviation for e_πi(x_i)a_{πi−1 πi}: the contribution of position x to the forward probability.

One can write the total probability of a sequence x under a given HMM, i.e. the forward probability, as a sum over paths π (1) (For the Viterbi algorithm we would replace the summation with argmax.) As written, this corresponds to a single, monolithic HMM, and we are implicitly summing over all paths through all alleles in the V, D, and J segments. In order to factorize this monolithic probability, we first write the probability of each path in more detail as a product over each position i in the sequence of length L: Here π_i is the state at position i in path π, and x_i is the symbol at position i in the query sequence. Thus e_πi(x_i) is the probability of emitting x_i from state π_i, and a_{πi−1 πi} is the transition probability from the state at i − 1 to the state at i.

We now subdivide this product for the path π into three factors for the V, D, and J segments; this divides the sequence correspondingly into three sections of length l_V, l_D, and L − l_V − l_D. We will use P_R(x, π, l_V, l_D) to denote the forward probability of the path π through a single segment R ∈ [V, D, J]. We then use this factorization to rearrange the order of operations in the sum over paths Eq (1): where q_g is the probability of choosing each allele g. Here we have isolated the computationally expensive sum over all states ∑_π∈g as far to the right as possible, so that we sum only over the paths within each allele, and combine all alleles afterward. Factorization thus reduces a single HMM with a state for each germline position in each of a few hundred alleles, to a number of HMMs, each with states only for a single allele. Since at each step in the forward (and Viterbi) recursion relations we sum over all possible previous states for each current state, computing time scales roughly as the square of the number of states in each HMM. By reducing the maximum number of states per HMM by several orders of magnitude, factorization thus substantially decreases memory and computation time.

N-additions change this picture very little: we simply add them to the left side of each D and J HMM (they could as easily go on the right side of V and D). The resulting HMM topologies are shown in Fig 11. In this version, we show a single insert state, with emission probabilities corresponding to the empirical N-region nucleotide distribution from data (compare Fig 12).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 12. HMM N-region topology.

By using four states instead of one, this gives improved discrimination for pairs or tuples of sequences because it does not ignore mutation information within N-regions. Self-transitions for insert states ommitted for clarity.

https://doi.org/10.1371/journal.pcbi.1004409.g012

As described above, the HMM does not model insertion/deletion mutations within gene segments at this time. Their inclusion would impose a significant computational burden: rather than a linear number of transitions there would be a quadratic number, and adding deletion self-transitions would require exploring the complete collection of potential deletions at every site in order to get a valid forward probability. Noting that the Smith-Waterman step provides only slightly less accurate annotation than the HMM, we instead provide the option of filtering out potential insertion/deletion mutations during the initial Smith-Waterman step. This allows the user to make a subjective decision, which we believe is appropriate in the face of the currently incomplete germline sequence databases, combined with many germline genes being related to each other by insertion/deletion events. We thus we provide a command line parameter to adjust the Smith-Waterman gap-opening penalty to vary sensitivity to insertion/deletion mutations. Any candidate insertion/deletion mutations are then flagged, after which the HMM can be run with and without the insertion/deletion.

Multi-HMMs.

As described above, ham is able to do inference under a model which simultaneously emits an arbitrary number of symbols k. When k = 2 this is typically called a pair HMM [23], and we call the generalized form a multi-HMM (k ≥ 2). One can also think of this as doing inference while constraining all of the sequences to come from the same path through the hidden states of the HMM. In our setting, the k sequences resulting from such a multi-HMM model are the various sequences deriving from a single rearrangement event (which differ only according to point substitution from somatic hypermutation).

We can use this ability to perform improved inference on a collection of sequences deriving from the same rearrangement event, allowing us to integrate out much of the uncertainty due to somatic hypermutation in each single sequence. In other words, not all mutations are shared between clonally related sequences, and this provides valuable information that is only available if the HMM can emit several sequences simultaneously.

Although this approach allows us to share inferential power among various sequences within the germline regions, with a standard VDJ HMM topology (as in Fig 11) the N-region does not contribute to the likelihood in a meaningful way. In order to allow likelihood contributions from the N-region, we replace the single insert state with four states, corresponding to naive-sequence N-addition of A, C, G, and T (Fig 12). The emissions of these four states are then treated as for actual germline states (Fig 10): the A state, for example, has a large probability of emitting an A, and a complementary probability (equal to the observed mutation probability) of emitting one of the other three bases. For example, if we pass in five sequences that share identical N-regions except that one sequence has a single mutated base, the HMM uses the information from the four non-mutated bases to conclude that the difference in the fifth sequence is likely to be a mutation from the un-mutated ancestral sequence.

Parameter estimation.

The parameters of our HMM consist of allele usage probabilities, transition probabilities, and emission probabilities; as described above we estimate categorical distributions for each of these. The inferred distributions of these parameters come from either a previous generation of HMM estimates, or from Smith-Waterman (as described below).

In order to convert from substitution probability p to emission probabilities, we set the probability of emission for each non-germline base to p/3, and correspondingly set the probability of germline emission to 1 − p. In the HMM implementation, it is trivial to account for different probabilities of mutating to different bases (instead of simply using f/3 for all three). However, we do not know of phylogenetic sequence simulation software (we use bppseqgen from Bio++ [53]) that implements both this and per-position mutation rates, and thus lacking reliable means of validation for this feature we leave it out.

Transition probabilities are set according to empirical frequencies of inferred exonuclease deletion and N-region lengths. For example, again sub-setting by allele, the frequency with which we observe a 3’ exonuclease deletion of length one gives us the transition probability from the second-to-last state in this allele to the end state (thereby bypassing the last state in the allele). This logic is repeated for all positions in each allele, and also for the 5’ end (where instead of a transition to the end state, it is a transition from the initial state). Note that we include 5’ V and 3’ D exonuclease deletions as a convenience (dashed lines in Fig 11) to account for varying read lengths. The N-region state self-transition probability is set to the inverse of the observed mean N-region length in data, and thus N-region lengths are modeled according to a geometric distribution with the correct mean length. While the choice of a geometric distribution is simply a result of HMMs’ inherent lack of memory, in practice we observe that N-region lengths are not far from geometrically distributed (Fig 4).

Finally, the allele choice probabilities denoted q_g above are simply set to the observed frequency of each allele.

For all parameters, we perform an initial estimation step using the Smith-Waterman based methods of [38]. These provisional parameters are used to build a set of HMMs which we then run on the same data in order to obtain a more accurate set of parameters. We can feed these parameters back into the HMM and continue the process recursively (this is Viterbi training in the language of [23]), but in practice we find no significant improvement after the first iteration. In future versions we may implement full Baum-Welch parameter estimation [23]. However, given the level of agreement which we observe for Viterbi training, we do not expect large improvement from moving to full Baum-Welch.

In order to correctly estimate parameter uncertainties we would like to know the sample size: the number of independent rearrangement events. This is not the same as the number of unique reads, because several reads can stem from a single rearrangement through somatic hypermutation and clonal expansion. In principle the sample size for each measurement should be the number of observed rearrangement events. However, we can only observe sequences rather than rearrangement events, and thus do not know precisely how many rearrangement events we have observed. Previous work has shown that a significant majority of B cell rearrangements are represented by only one sequence in healthy humans, even in a deep sample from the memory compartment [54]. In order to be conservative we posit that B-cells are members of clones with two members, and thus multiply all uncertainty measurements (e.g. in Fig 2) by a factor of corresponding to this assumed two-fold reduction in sample size.

Parameter merging in small samples via tiered aggregation.

As mentioned above, a more highly parameterized model is both allowed by and requires large data sets. In order to facilitate the use of partis on data sets of varying size, and also to allow accurate inference of rare clones, we have thus implemented a scheme that automatically reduces the detail of the model on smaller samples. The basic idea of this scheme, which we call “tiered aggregation”, is to merge together the information from increasing numbers of germline alleles, in several tiers of similarity, as the sample size decreases.

As shown above, we observe significant parameter variation between alleles, and we thus initially subset all emission and transition probabilities by allele (i.e. use different probabilities for each allele of each gene in V, D, and J). For large data sets, and for BCR repertoires with relatively homogeneous allele frequency distributions, this approach is sufficient. If we observe a particular allele only a handful of times, however, we cannot confidently estimate parameters for that allele. In such cases we thus include information from similar alleles in the parameter estimation.

Specifically, if we observe an allele fewer than N times, we take a simple average over all the observations of its allelic variants when calculating its parameters, rather than just considering that allele. If we also fail to observe N occurrences of all these allelic variants together, we go on to include all alleles in the same IMGT gene family (e.g. all IGHV1 alleles). Finally, if with this criterion we still do not reach N observations, we include all alleles from that segment (e.g. all V alleles). Here N is a tunable parameter, and in practice gives good results in simulation at about 20, which is the value used for the results in this paper.

This procedure thus has the effect of automatically compensating for decreased parameter accuracy in smaller samples by switching to a less parameter-rich model. We find this strategy to be effective in simulation (Fig 9). As expected, performance decreases with decreasing sample size, although the degradation is minimal for samples larger than a few hundred sequences. While partis still performs well on fewer than a few hundred sequences, there is little benefit to using it, as one is not taking advantage of its detailed models. Instead, one could use ighutil [38] on small data sets, as in such cases the two will perform comparably in terms of accuracy.

Validation.

As described above, we find it necessary to validate BCR annotation methods on simulated sequences; we therefore wrote a simulator of rearrangement and somatic hypermutation. This simulator takes as input a joint categorical distribution over all “rearrangement values” which are necessary to specify the rearrangement event (e.g. 3’ V exonuclease deletion length, which V allele, etc.). It then draws a point in this space according to the distribution, and generates a naive sequence according to the coordinates of this point. N-regions are generated with corresponding length, with N-addition bases chosen randomly according to the empirical nucleotide distribution. This simulation process implicitly models all correlations between “rearrangement values,” even correlations that are ignored in the HMMs. As an input distribution of rearrangement values to the simulation, we used our inferences on the Adaptive data set.

The resulting unmutated ancestor then diversifies via simulated mutation into a set of sequences in a clonal family. Specifically, we first use TreeSim [55] to generate a lineage tree descending from this ancestral sequence, with a speciation rate of 1.0 and extinction rate of 0.5, conditioned on the desired number of leaves and on a tree height drawn from the empirical distribution. The number of leaves is easily configurable in our simulation package either as a constant or as a random variable drawn from some distribution.

The segments are then generated through simulation down this tree using empirical per-position mutation rates, with tree height rescaled by the mean observed ratio of that segment’s mutation rate to the rate in all three segments, using the bppseqgen mutation simulator in the Bio++ [53] package. The D segment, for instance, could use a tree height 1.8 times the overall height in a typical human, while the V and J would use 0.98 and 0.87. N-regions are also mutated, using parameters averaged over the three segments. This approach yields good agreement between mutation rates in data and simulation (S6 Fig).

For simplicity, all plots in this paper use simulation with a constant five leaves per tree; results were consistent when simulating with widely varying constant, as well as non-constant, leaves per tree (results not shown). The sample for which we show performance comparisons (Table 2 and Figs 6, 7 and 8) was generated with parameters from human A in the Adaptive data set, except that the mean mutation frequency was doubled (see the original mutation frequencies for the three humans in S6 Fig) in order to provide a more challenging inference test.

To check that this simulator generates sequences that are close to real data, we compared its output parameter distributions to the inferred parameters from data (which are the simulator’s input). These distributions are similar (S5, S6 and S7 Figs), showing that the simulator accurately recapitulates the processes generating the true data. Given this accuracy, the compatibility between true and inferred distributions in Fig 8 shows that our original parameters inferred from data are indeed close to the true parameters in data.

The validation is run within the partis directory in the main repository using the command scons validate.

We emphasize that this simulator’s only inputs are the inferred empirical parameter distributions, and that it is thus entirely independent of partis’ HMM machinery. partis’s inference framework, meanwhile, is presented with only the simulated sequences; specifically, it has no information about the simulation or its parameters (information which would not be available in a real data set).