Extensive hyperpolymorphism and sequence similarity between the HLA genes make HLA type inference from whole-genome sequencing data a challenging problem. We address these by representing sequences from over 10,000 known alleles in a reference graph structure, enabling accurate read mapping. HLA*PRG, our algorithm, outperforms existing methods by a wide margin and for the first time consistently achieves the accuracy of gold-standard reference methods with one error across 158 alleles tested.
Host-pathogen co-evolution and the emergence of broadly neutralizing antibodies in chronic infections
Armita Nourmohammad, Jakub Otwinowski, Joshua B. Plotkin
The vertebrate adaptive immune system provides a flexible and diverse set of molecules to neutralize pathogens. Yet, viruses that cause chronic infections, such as HIV, can survive by evolving as quickly as the adaptive immune system, forming an evolutionary arms race within a host. Here we introduce a mathematical framework to study the co-evolutionary dynamics of antibodies with antigens within a patient. We focus on changes in the binding interactions between the antibody and antigen populations, which result from the underlying stochastic evolution of genotype frequencies driven by mutation, selection, and drift. We identify the critical viral and immune parameters that determine the distribution of antibody-antigen binding affinities. We also identify definitive signatures of co-evolution that measure the reciprocal response between the antibody and viruses, and we introduce experimentally measurable quantities that quantify the extent of adaptation during continual co-evolution of the two opposing populations. Finally, we analyze competition between clonal lineages of antibodies and characterize the fate of a given lineage dependent on the state of the antibody and viral populations. In particular, we derive the conditions that favor the emergence of broadly neutralizing antibodies, which may be used in designing a vaccine against HIV.
Finite-size effects and switching times for Moran dynamics with mutation
Lee DeVille, Meghan Galiardi
We consider the Moran process with two populations competing under an iterated Prisoners’ Dilemma in the presence of mutation, and concentrate on the case where there are multiple Evolutionarily Stable Strategies. We perform a complete bifurcation analysis of the deterministic system which arises in the infinite population size. We also study the Master equation and obtain asymptotics for the invariant distribution and metastable switching times for the stochastic process in the case of large but finite population. We also show that the stochastic system has asymmetries in the form of a skew for parameter values where the deterministic limit is symmetric.
Reduction rules for the maximum parsimony distance on phylogenetic trees
Steven Kelk, Mareike Fischer, Vincent Moulton, Taoyang Wu
In phylogenetics, distances are often used to measure the incongruence between a pair of phylogenetic trees that are reconstructed by different methods or using different regions of genome. Motivated by the maximum parsimony principle in tree inference, we recently introduced the maximum parsimony (MP) distance, which enjoys various attractive properties due to its connection with several other well-known tree distances, such as TBR and SPR. Here we show that computing the MP distance between two trees, a NP-hard problem in general, is fixed parameter tractable in terms of the TBR distance between the tree pair. Our approach is based on two reduction rules–the chain reduction and the subtree reduction–that are widely used in computing TBR and SPR distances. More precisely, we show that reducing chains to length 4 (but not shorter) preserves the MP distance. In addition, we describe a generalization of the subtree reduction which allows the pendant subtrees to be rooted in different places, and show that this still preserves the MP distance. We conclude with an extended discussion in which we focus on similarities and differences between MP distance and TBR distance, and present a number of open problems.