A mean first passage time genome rearrangement distance.

This paper introduces a new way to define a genome rearrangement distance, using the concept of mean first passage time from probability theory. Crucially, this distance provides a genuine metric on genome space. We develop the theory and introduce a link to a graph-based zeta function. The approach is very general and can be applied to a wide variety of group-theoretic models of genome evolution.

Position and Content Paradigms in Genome Rearrangements: The Wild and Crazy World of Permutations in Genomics.

Modellers of large-scale genome rearrangement events, in which segments of DNA are inverted, moved, swapped, or even inserted or deleted, have found a natural syntax in the language of permutations. Despite this, there has been a wide range of modelling choices, assumptions and interpretations that make navigating the literature a significant challenge. Indeed, even authors of papers that use permutations to model genome rearrangement can struggle to interpret each others' work, because of subtle differences in basic assumptions that are often deeply ingrained (and consequently sometimes not even mentioned). In this paper, we describe the different ways in which permutations have been used to model genomes and genome rearrangement events, presenting some features and limitations of each approach, and show how the various models are related. This paper will help researchers navigate the landscape of permutation-based genome rearrangement models and make it easier for authors to present clear and consistent models.

Maximum likelihood estimates of pairwise rearrangement distances.

Accurate estimation of evolutionary distances between taxa is important for many phylogenetic reconstruction methods. Distances can be estimated using a range of different evolutionary models, from single nucleotide polymorphisms to large-scale genome rearrangements. Corresponding corrections for genome rearrangement distances fall into 3 categories: Empirical computational studies, Bayesian/MCMC approaches, and combinatorial approaches. Here, we introduce a maximum likelihood estimator for the inversion distance between a pair of genomes, using a group-theoretic approach to modelling inversions introduced recently. This MLE functions as a corrected distance: in particular, we show that because of the way sequences of inversions interact with each other, it is quite possible for minimal distance and MLE distance to differently order the distances of two genomes from a third. The second aspect tackles the problem of accounting for the symmetries of circular arrangements. While, generally, a frame of reference is locked, and all computation made accordingly, this work incorporates the action of the dihedral group so that distance estimates are free from any a priori frame of reference. The philosophy of accounting for symmetries can be applied to any existing correction method, for which examples are offered.

Which Phylogenetic Networks are Merely Trees with Additional Arcs?

A binary phylogenetic network may or may not be obtainable from a tree by the addition of directed edges (arcs) between tree arcs. Here, we establish a precise and easily tested criterion (based on "2-SAT") that efficiently determines whether or not any given network can be realized in this way. Moreover, the proof provides a polynomial-time algorithm for finding one or more trees (when they exist) on which the network can be based. A number of interesting consequences are presented as corollaries; these lead to some further relevant questions and observations, which we outline in the conclusion.

Algebraic double cut and join : A group-theoretic approach to the operator on multichromosomal genomes.

Establishing a distance between genomes is a significant problem in computational genomics, because its solution can be used to establish evolutionary relationships including phylogeny. The "double cut and join" (DCJ) model of chromosomal rearrangement proposed by Yancopoulos et al. (Bioinformatics 21:3340-3346, 2005) has received attention as it can model inversions, translocations, fusion and fission on a multichromosomal genome that may contain both linear and circular chromosomes. In this paper, we realize the DCJ operator as a group action on the space of multichromosomal genomes. We study this group action, deriving some properties of the group and finding group-theoretic analogues for the key results in the DCJ theory.

An algebraic view of bacterial genome evolution.

Rearrangements of bacterial chromosomes can be studied mathematically at several levels, most prominently at a local, or sequence level, as well as at a topological level. The biological changes involved locally are inversions, deletions, and transpositions, while topologically they are knotting and catenation. These two modelling approaches share some surprising algebraic features related to braid groups and Coxeter groups. The structural approach that is at the core of algebra has long found applications in sciences such as physics and analytical chemistry, but only in a small number of ways so far in biology. And yet there are examples where an algebraic viewpoint may capture a deeper structure behind biological phenomena. This article discusses a family of biological problems in bacterial genome evolution for which this may be the case, and raises the prospect that the tools developed by algebraists over the last century might provide insight to this area of evolutionary biology.

Group-theoretic models of the inversion process in bacterial genomes.

The variation in genome arrangements among bacterial taxa is largely due to the process of inversion. Recent studies indicate that not all inversions are equally probable, suggesting, for instance, that shorter inversions are more frequent than longer, and those that move the terminus of replication are less probable than those that do not. Current methods for establishing the inversion distance between two bacterial genomes are unable to incorporate such information. In this paper we suggest a group-theoretic framework that in principle can take these constraints into account. In particular, we show that by lifting the problem from circular permutations to the affine symmetric group, the inversion distance can be found in polynomial time for a model in which inversions are restricted to acting on two regions. This requires the proof of new results in group theory, and suggests a vein of new combinatorial problems concerning permutation groups on which group theorists will be needed to collaborate with biologists. We apply the new method to inferring distances and phylogenies for published Yersinia pestis data.

Evolution of variation in presence and absence of genes in bacterial pathways.

BACKGROUND: Bacterial genomes exhibit a remarkable degree of variation in the presence and absence of genes, which probably extends to the level of individual pathways. This variation may be a consequence of the significant evolutionary role played by horizontal gene transfer, but might also be explained by the loss of genes through mutation. A challenge is to understand why there would be variation in gene presence within pathways if they confer a benefit only when complete. RESULTS: Here, we develop a mathematical model to study how variation in pathway content is produced by horizontal transfer, gene loss and partial exposure of a population to a novel environment. CONCLUSIONS: We discuss the possibility that variation in gene presence acts as cryptic genetic variation on which selection acts when the appropriate environment occurs. We find that a high level of variation in gene presence can be readily explained by decay of the pathway through mutation when there is no longer exposure to the selective environment, or when selection becomes too weak to maintain the genes. In the context of pathway variation the role of horizontal gene transfer is probably the initial introduction of a complete novel pathway rather than in building up the variation in a genome without the pathway.

The epidemiological fitness cost of drug resistance in Mycobacterium tuberculosis.

The emergence of antibiotic resistance in Mycobacterium tuberculosis has raised the concern that pathogen strains that are virtually untreatable may become widespread. The acquisition of resistance to antibiotics results in a longer duration of infection in a host, but this resistance may come at a cost through a decreased transmission rate. This raises the question of whether the overall fitness of drug-resistant strains is higher than that of sensitive strains--essential information for predicting the spread of the disease. Here, we directly estimate the transmission cost of drug resistance, the rate at which resistance evolves, and the relative fitness of resistant strains. These estimates are made by using explicit models of the transmission and evolution of sensitive and resistant strains of M. tuberculosis, using approximate Bayesian computation, and molecular epidemiology data from Cuba, Estonia, and Venezuela. We find that the transmission cost of drug resistance relative to sensitivity can be as low as 10%, that resistance evolves at rates of approximately 0.0025-0.02 per case per year, and that the overall fitness of resistant strains is comparable with that of sensitive strains. Furthermore, the contribution of transmission to the spread of drug resistance is very high compared with acquired resistance due to treatment failure (up to 99%). Estimating such parameters directly from in vivo data will be critical to understanding and responding to antibiotic resistance. For instance, projections using our estimates suggest that the prevalence of tuberculosis may decline with successful treatment, but the proportion of cases associated with resistance is likely to increase.

Conditions for the evolution of gene clusters in bacterial genomes.

Genes encoding proteins in a common pathway are often found near each other along bacterial chromosomes. Several explanations have been proposed to account for the evolution of these structures. For instance, natural selection may directly favour gene clusters through a variety of mechanisms, such as increased efficiency of coregulation. An alternative and controversial hypothesis is the selfish operon model, which asserts that clustered arrangements of genes are more easily transferred to other species, thus improving the prospects for survival of the cluster. According to another hypothesis (the persistence model), genes that are in close proximity are less likely to be disrupted by deletions. Here we develop computational models to study the conditions under which gene clusters can evolve and persist. First, we examine the selfish operon model by re-implementing the simulation and running it under a wide range of conditions. Second, we introduce and study a Moran process in which there is natural selection for gene clustering and rearrangement occurs by genome inversion events. Finally, we develop and study a model that includes selection and inversion, which tracks the occurrence and fixation of rearrangements. Surprisingly, gene clusters fail to evolve under a wide range of conditions. Factors that promote the evolution of gene clusters include a low number of genes in the pathway, a high population size, and in the case of the selfish operon model, a high horizontal transfer rate. The computational analysis here has shown that the evolution of gene clusters can occur under both direct and indirect selection as long as certain conditions hold. Under these conditions the selfish operon model is still viable as an explanation for the evolution of gene clusters.

A discussion on the process of defining 2-D separation selectivity.

In this manuscript, we investigate the importance that must be placed on the selection of standard compounds when undertaking studies to optimize the performance of 2-D-HPLC separations. A geometric approach to factor analysis and a measure of peak density across the separation space were applied to assess localized measures of component distributions within the 2-D separation plane. The results of this analysis of data showed that the measure of separation quality varied markedly, depending on the elution zone for which the test was undertaken. The study concluded that if standards cannot be obtained that adequately describe the entire sample matrix, the sample itself should be used, and also, the separation should be optimized for regions of interest, not necessarily the separation as a whole.

MERCAT: Visualising molecular epidemiology data combining genetic markers and drug resistance profiles.

Molecular epidemiology uses genetic information from bacterial isolates to shed light on the population structure and dynamics of pathogens. Bacterial pathogens can now be studied by whole genome sequencing, but for some well-studied pathogens such as Mycobacterium tuberculosis a wealth of information is also available from other sources such as spoligotyping and multi-locus variable-number-tandem-repeats (VNTR). Isolates are also frequently tested for susceptibility to antibiotics. Methods of analysis are available for each type of data but it would be informative to combine multiple sources of information into a single analysis or visualisation. Here, we propose and implement a simple way to visualise genotypes along with drug resistance profiles for multiple drugs. We also present a way to combine information from different markers to aid in visualising relationships among isolates. These methods help to reveal the origins and spread of multi-drug resistant lineages of pathogens. We introduce a new computational package, MERCAT (Molecular Epidemiology Researcher's Collection of Analytical Tools), for analysing genotypic data from bacterial isolates. The software is available as an open source package in the statistical language R with a user-friendly interface using R Shiny. Although we focus on tuberculosis and the major molecular markers used to understand tuberculosis transmission - multilocus VNTR-typing (MLVA or MIRU) and spoligotyping - the methods and tools can be applied to other bacteria and can be easily tailored to other genetic markers such as SNP data from whole genome sequencing.

spolTools: online utilities for analyzing spoligotypes of the Mycobacterium tuberculosis complex.

spolTools is a collection of online programs designed to manipulate and analyze spoligotype datasets of the Mycobacterium tuberculosis complex. These tools are integrated into a repository currently containing 1179 spoligotypes and 6278 isolates across 30 datasets. Users can search this database to export for external use or to pass on to the integrated tools. These tools include the computation of basic population genetic quantities, the visualization of clusters of spoligotype patterns based on an estimated evolutionary history and a procedure to predict emerging strains - genotypes associated with elevated transmission.

Models of deletion for visualizing bacterial variation: an application to tuberculosis spoligotypes.

BACKGROUND: Molecular typing methods are commonly used to study genetic relationships among bacterial isolates. Many of these methods have become standardized and produce portable data. A popular approach for analyzing such data is to construct graphs, including phylogenies. Inferences from graph representations of data assist in understanding the patterns of transmission of bacterial pathogens, and basing these graph constructs on biological models of evolution of the molecular marker helps make these inferences. Spoligotyping is a widely used method for genotyping isolates of Mycobacterium tuberculosis that exploits polymorphism in the direct repeat region. Our goal was to examine a range of models describing the evolution of spoligotypes in order to develop a visualization method to represent likely relationships among M. tuberculosis isolates. RESULTS: We found that inferred mutations of spoligotypes frequently involve the loss of a single or very few adjacent spacers. Using a second-order variant of Akaike's Information Criterion, we selected the Zipf model as the basis for resolving ambiguities in the ancestry of spoligotypes. We developed a method to construct graphs of spoligotypes (which we call spoligoforests). To demonstrate this method, we applied it to a tuberculosis data set from Cuba and compared the method to some existing methods. CONCLUSION: We propose a new approach in analyzing relationships of M. tuberculosis isolates using spoligotypes. The spoligoforest recovers a plausible history of transmission and mutation events based on the selected deletion model. The method may be suitable to study markers based on loci of similar structure from other bacteria. The groupings and relationships in the spoligoforest can be analyzed along with the clinical features of strains to provide an understanding of the evolution of spoligotypes.

Interpreting genotype cluster sizes of Mycobacterium tuberculosis isolates typed with IS6110 and spoligotyping.

Molecular techniques such as IS6110-RFLP typing and spacer oligonucleotide typing (spoligotyping) have aided in understanding the transmission patterns of Mycobacterium tuberculosis. The degree of clustering of isolates on the basis of genotypes is informative of the extent of transmission in a given geographic area. We analyzed 130 published data sets of M. tuberculosis isolates, each representing a sample of bacterial isolates from a specific geographic region, typed with either or both of the IS6110-RFLP and spoligotyping methods. We explored common features and differences among these samples. Using population models, we found that the presence of large clusters (typically associated with recent transmission) as well as a large number of singletons (genotypes found exactly once in the data set) is consistent with an expanding infectious population. We also estimated the mutation rate of spoligotype patterns relative to IS6110 patterns and found the former rate to be about 10-26% of the latter. This study illustrates the utility of examining the full distribution of genotype cluster sizes from a given region, in the light of population genetic models.

Using approximate Bayesian computation to estimate tuberculosis transmission parameters from genotype data.

Tuberculosis can be studied at the population level by genotyping strains of Mycobacterium tuberculosis isolated from patients. We use an approximate Bayesian computational method in combination with a stochastic model of tuberculosis transmission and mutation of a molecular marker to estimate the net transmission rate, the doubling time, and the reproductive value of the pathogen. This method is applied to a published data set from San Francisco of tuberculosis genotypes based on the marker IS6110. The mutation rate of this marker has previously been studied, and we use those estimates to form a prior distribution of mutation rates in the inference procedure. The posterior point estimates of the key parameters of interest for these data are as follows: net transmission rate, 0.69/year [95% credibility interval (C.I.) 0.38, 1.08]; doubling time, 1.08 years (95% C.I. 0.64, 1.82); and reproductive value 3.4 (95% C.I. 1.4, 79.7). These figures suggest a rapidly spreading epidemic, consistent with observations of the resurgence of tuberculosis in the United States in the 1980s and 1990s.

An evaluation of indices for quantifying tuberculosis transmission using genotypes of pathogen isolates.

BACKGROUND: Infectious diseases are often studied by characterising the population structure of the pathogen using genetic markers. An unresolved problem is the effective quantification of the extent of transmission using genetic variation data from such pathogen isolates. METHODS: It is important that transmission indices reflect the growth of the infectious population as well as account for the mutation rate of the marker and the effects of sampling. That is, while responding to this growth rate, indices should be unresponsive to the sample size and the mutation rate. We use simulation methods taking into account both the mutation and sampling processes to evaluate indices designed to quantify transmission of tuberculosis. RESULTS: Previously proposed indices generally perform inadequately according to the above criteria, with the partial exception of the recently proposed Transmission-Mutation Index. CONCLUSION: Any transmission index needs to take into account mutation of the marker and the effects of sampling. Simple indices are unlikely to capture the full complexity of the underlying processes.

Methods of quantifying and visualising outbreaks of tuberculosis using genotypic information.

Genotypic data from pathogenic isolates are often used to measure the extent of infectious disease transmission. These methods include phylogenetic reconstruction and the evaluation of clustering indices. The first aim of this paper is to critique current methods used to analyse genotypic data from molecular epidemiological studies of tuberculosis. In particular, by not accounting for the mutation rate of markers, errors arise in making inferences about outbreaks based on genotypic information. The second aim is to suggest a new way to represent genotypic data visually, involving graphs and trees. We also discuss some interpretations and modifications of existing indices. Although our focus is tuberculosis, the methods we discuss are generally applicable to any directly transmissible clonal pathogen.

Tree-like reticulation networks--when do tree-like distances also support reticulate evolution?

Hybrid evolution and horizontal gene transfer (HGT) are processes where evolutionary relationships may more accurately be described by a reticulated network than by a tree. In such a network, there will often be several paths between any two extant species, reflecting the possible pathways that genetic material may have been passed down from a common ancestor to these species. These paths will typically have different lengths but an 'average distance' can still be calculated between any two taxa. In this article, we ask whether this average distance is able to distinguish reticulate evolution from pure tree-like evolution. We consider two types of reticulation networks: hybridisation networks and HGT networks. For the former, we establish a general result which shows that average distances between extant taxa can appear tree-like, but only under a single hybridisation event near the root; in all other cases, the two forms of evolution can be distinguished by average distances. For HGT networks, we demonstrate some analogous but more intricate results.

Detecting emerging strains of tuberculosis by using spoligotypes.

The W-Beijing strain of tuberculosis has been identified in many molecular epidemiological studies as being particularly prevalent. This identification has been made possible through the development of a number of genotyping technologies including spoligotyping. Highly prevalent genotypes associated with outbreaks, such as the W-Beijing strain, are implicitly regarded as fast spreading. Here we present a quantitative method to identify "emerging" strains, those that are spreading faster than the background rate inferred from spoligotype data. The approach uses information about the mutation process specific to spoligotypes, combined with a model of both transmission and mutation. The core principle is that if two comparable strains have the same number of isolates, then the strain with fewer inferred mutation events must have spread faster if the mutation process is common. Applying this method to four different data sets, we find not only the W-Beijing strain, but also a number of other strains, to be emerging in this sense. Importantly, the strains that are identified as emerging are not simply those with the largest number of cases. The use of this method should facilitate the targeting of individual genotypes in intervention programs.