text:
## Main

A tumour is a product of somatic evolution in which mutation, selection, genetic drift and cell dispersal generate a patchwork of cell subpopulations (clones) with varying degrees of aggressiveness and treatment sensitivity1. A primary goal of modern cancer research is to characterize this evolutionary process to enable precise, patient-specific prognoses and optimize targeted therapy regimens. However, studies revealing the evolutionary features of particular cancers raise as many questions as they answer. Why do different tumour types exhibit different modes of evolution2,3,4,5,6,7,8? What conditions sustain the frequently observed pattern of branching evolution, in which clones diverge and evolve in parallel2,9,10,11? And why do some pan-cancer analyses indicate that many tumours evolve neutrally12, whereas others support extensive selection13?

Factors proposed as contributing to tumour evolution include microenvironmental heterogeneity, niche construction and positive ecological interactions between clones1,14,15,16,17. However, because such factors have not been well characterized across human cancer types, it remains unclear how they might relate to evolutionary modes. In contrast, it is well established that tumours exhibit a wide range of architectures and types of cell dispersal18,19 (Fig. 1), the evolutionary effects of which have not been systematically examined. Because gene flow (the transfer of genetic information between localized populations20) is a principal force in evolutionary dynamics, we hypothesized that different tumour structures might result in different evolutionary modes. To test this hypothesis, we developed a way to formulate multiple classes of mathematical models, each tailored to a different class of tumour, within a single general framework, and we implemented this framework as a stochastic computer programme.

Our modelling approach is built on basic tenets of cancer evolutionary theory1. Simulated tumours arise from a single cell that has acquired a fitness-enhancing mutation. Each time a tumour cell divides, its daughter cells can acquire passenger mutations, which have no fitness effect, and more rarely driver mutations, which confer a fitness advantage. In solid tumours, we assume that cells compete with one another for space and other resources. Whereas previous studies have assumed that tumours grow into empty space, our model also allows us to simulate the invasion of normal tissue—a defining feature of malignancy.

## Results

### Tumour architecture can determine the mode of evolution

To test whether varying tumour architecture suffices to alter the tumour evolutionary mode, we considered four particular models with different spatial structures and manners of cell dispersal but identical evolutionary parameters (driver mutation rate and distribution of driver fitness effects). We set the dispersal probability per cell division such that all tumours take a similar amount of time to grow from one cell to one million cells, corresponding to several years in real time.

Our first case is a non-spatial model that has been proposed as appropriate to leukaemia21,22, a tumour type in which mutated stem cells in semi-solid bone marrow produce cancer cells that mix and proliferate in the bloodstream (Fig. 1a). When simulating tumour growth in the absence of spatial constraints, rapid clonal expansions can result from driver mutations that increase the cell division rate by as little as a few percent, and the vast majority of cells eventually share the same set of driver mutations (Fig. 2a–d). These characteristics are reminiscent of chronic myeloid leukaemia, in which cell proliferation is driven by a single change to the genome23, and acute myeloid leukaemia, which has relatively few drivers24.

In our second model, consistent with the biology of colorectal adenoma25 and in common with previous computational models of colorectal carcinoma5,26,27, we simulate a tumour that consists of large glands (Fig. 1b) and grows via gland fission (bifurcation). Although the driver mutation rate and the fitness effect are exactly the same as in the previous case, the addition of spatial structure dramatically alters the mode of tumour evolution. The organization of cells into glands limits the extent to which driver mutations can spread through the population, so that selective sweeps become progressively localized as the tumour expands. For our parameter values, this process leads to a highly branched, fan-like driver phylogenetic tree and ever greater spatial diversity, with different combinations of driver mutations predominating even in neighbouring glands (Fig. 2e–h). The mean tumour cell fitness increases substantially, but there is also extensive, positively correlated intratumour variation in cell fitness values and passenger mutation counts (Extended Data Fig. 1a–b). Model outcomes are similar even if cells are able to acquire drivers that directly increase the gland fission rate, because such mutations rarely spread within glands (Extended Data Fig. 2a).

The third case corresponds to a glandular tumour that grows by invading adjacent normal tissue, as documented in various types of solid tumour, including many colorectal, breast and lung cancers19,28. Glandular tumours are subdivided into localized cell communities (Fig. 1c), whose small size has previously been inferred by community detection methods29 and mathematical modelling.30 To obtain additional estimates of gland size in four cancer types, we used semi-automated analysis of histology slides (Extended Data Fig. 3) and found that each gland contains between a few hundred and a few thousand cells (Extended Data Fig. 4a). In simulations with gland sizes within this range, we find that even small increases in cell fitness can spark rapid clonal expansions. Clonal interference nevertheless inhibits selective sweeps, resulting in a zonal tumour in which large regions share the same combination of driver mutations (Fig. 2i–l and Extended Data Fig. 1c,d). Simulated invasive glandular tumours typically exhibit stepwise increases in driver diversity and a phylogeny with several long branches, qualitatively consistent with observations in numerous cancer types2,3,11. Restricting cell dispersal to the tumour boundary without dispersal within the tumour bulk (to simulate tumours that lack intratumoural budding28 or tumours in which proliferation is confined to the boundary31) results in somewhat shorter branches (Extended Data Fig. 2b).

Our fourth and final model represents a tumour with no glandular structure and with growth confined to its boundary (Fig. 1d). Expansive tumour growth associated with a clearly defined boundary and no sign of active migration occurs in tissues that impose relatively weak physical resistance18. Boundary-growth models have in particular been proposed as appropriate for simulating the evolution of certain kinds of hepatocellular carcinoma7,32, although it should be noted that hepatocellular carcinoma in general exhibits a wide range of growth patterns33. The spatial structure of the boundary-growth model favours genetic drift, rather than selection. For our fixed parameter values, tumour evolution in this case is effectively almost neutral (Fig. 2m–p and Extended Data Fig. 1e), and mutations can spread only by surfing on a wave of population expansion34,35,36. Consequently, the mutation burden generally increases from the tumour core to its boundary (Extended Data Fig. 1f). Selection is only slightly more prominent when cells can compete with their nearest neighbours within the tumour mass (Extended Data Fig. 2c). Suppression of selection in the boundary-growth model is consistent with evidence of effectively neutral evolution in hepatocellular carcinoma7, as well as the existence of large, well-differentiated benign tumours such as leiomyomas37 and fibroadenomas38 that only rarely progress to malignancy.

### Characterization of evolutionary modes and comparison with data

Together, our models demonstrate that variation in the range of cell–cell interactions and the manner of cell dispersal alone can generate distinct modes of tumour evolution. We next sought to describe these modes more precisely in terms of summary evolutionary indices that can be computed from both our simulations and real cancer genomic data (Fig. 3a). The first index we considered is clonal diversity (denoted D), which grows with the number of large nodes in the driver phylogenetic tree (as in the final column of Fig. 2). The second index n is the mean number of driver mutations per cell, which represents the average depth of the driver phylogenetic tree. Any pair of values of these two indices corresponds to a distinct set of phylogenetic trees. The nodes of these trees represent clones, and their size is proportional to clone population size. The space of attainable n and D values (Fig. 3b) is bounded below by the line D = 1 and above by the curve D = 1/(2−n)2 (see Methods). Locations close to the upper boundary correspond to more highly branched trees than locations close to the lower boundary, and locations on the left correspond to trees with shorter branches than locations on the right.

To compare our model outcomes to data, we determined the evolutionary indices of phylogenetic trees previously inferred from multi-region sequencing of four solid cancer types: clear cell renal cell carcinoma (ccRCC)9, non-small-cell lung cancer (NSCLC)10, breast cancer39 and mesothelioma40. We also calculated indices from single-cell sequencing data for breast cancer41 and uveal melanoma42. Despite their methodological diversity, these six studies yielded remarkably similar evolutionary indices. The majority of data points (28 of 35) lie above a trajectory corresponding to sequential selective sweeps (pink curve in Fig. 3b) and below a reference curve that represents an intermediate degree of branching (pale blue curve in Fig. 3b and Supplementary information). All the tumours have 1 < D < 12 and 3≤n < 14. Notwithstanding limitations of sampling, sequencing and phylogenetic inference methods, a useful computational model of invasive tumour evolution should generate summary indices that are consistent with these data points, corresponding to branching evolution with a small number of main branches.

The simulation results of the four models discussed previously form four distinct clusters with respect to the summary indices n and D (Fig. 3c; mean silhouette width 0.60). Neutral counterparts of these four models—which have the same parameter values, except that the driver fitness effect is reduced to zero—cluster together, near the boundary-growth model. As expected, we find that the evolutionary indices of the solid tumours are consistent with outcomes of our invasive glandular model, and this consistency is robust to varying gland size, driver mutation rate and driver mutation effect within plausible ranges (Extended Data Fig. 5). Particularly close agreement between unadjusted model output and data occurs when the average driver fitness effect is 0.2 (Fig. 3d).

An important caveat in the above comparison is that the unadjusted model output includes all driver mutations down to a frequency of one in a million, whereas solid tumour sequencing protocols fail to detect most mutations at frequencies below 5%9. This difference in sensitivity means that D values calculated from data are expected to underestimate true tumour diversity. It follows that a fairer comparison can be made by removing rare mutations from the model output, to simulate imperfect sensitivity. Such adjustment strengthens the agreement between model and data (Fig. 3e and Extended Data Fig. 6).

Since the non-spatial model most plausibly represents liquid tumour evolution, we compared its predictions to additional data for acute myeloid leukaemia24. We found robust correspondence between the model and this data set (Fig. 3b,c and Supplementary Fig. 1). Within plausible parameter ranges, 83% of tumours simulated using a non-spatial model have coordinates (n, D) consistent with the selective-sweeps evolutionary mode.

Alternative models that have different spatial structures are less consistent with data for both solid and liquid tumours. For the gland fission model, 83% of simulated tumours have coordinates above the intermediate-branching curve, corresponding to high values of D relative to n (Supplementary Fig. 2). For the boundary-growth model, both n and D are typically close to 1 (Supplementary Fig. 3). These outcomes are summarized in Table 1, which provides quantitative definitions of evolutionary modes in terms of evolutionary indices (see also Fig. 3f and Supplementary Table 1).

Results for a variant of the invasive glandular model, in which normal cells are absent and the tumour grows into empty space, are also less consistent with data (Supplementary Fig. 4). In this empty-space model, the speed at which the tumour expands (via cell dispersal into empty space) typically exceeds the speed at which clones spread within the tumour (via cell dispersal into fully occupied glands), which leads to a more star-shaped or highly branched phylogeny (high D relative to n). Conversely, when tumour cells must compete with normal cells at the tumour boundary (as in the third row of Fig. 2), the speed at which driver mutations spread within the tumour is similar to the speed of tumour growth, which enables some driver mutations to reach high frequency and results in sparser branching (Extended Data Fig. 5). Yet another alternative model, which includes normal cells but confines cell dispersal to the tumour boundary, thwarts the spread of driver mutations and generates similar D but smaller n values (Supplementary Fig. 5).

### Further analysis of tumour evolutionary modes

A complementary way to describe modes of tumour evolution is in terms of phylogenetic tree shape or balance. Because tree balance indices developed for characterizing organismal evolution are poorly suited to tumour data, we developed an index43 that is robust to variation in sampling and sequencing protocols (Methods). This index J1 takes a high value for trees in which branching events tend to split the tree into subtrees of similar size. Low values are assigned to trees that are approximately linear or are dominated by a single node.

Just as for indices n and D, the tree balance values predicted by our invasive glandular tumour model are consistent with the values obtained from sequencing data (Fig. 4a). Typical J1 values for both this model and the data are between 0 and 0.5—substantially below the maximum value of 1 corresponding to perfectly balanced trees. The consistency remains when we adjust the model output by removing rare driver mutations (Extended Data Fig. 6, which constitutes a fairer comparison), even though the associated trees appear very different (Extended Data Fig. 7) and have dissimilar degree distributions (Extended Data Fig. 8). Agreement between model and data is also observed for alternative balance indices after removing rare mutations (Supplementary Figs. 6, 7 and 8). Conversely, neutral models and models that do not account for glandular structure predict smaller or more variable tree balance values than the data for solid tumours (Fig. 4a). Tree balance values for the non-spatial model are consistent with data for acute myeloid leukaemia (Fig. 4a).

Whereas n, D and J1 are determined only by the final tumour state, other indices can be based on time series data. For example, the mean clonal turnover magnitude $$\overline{{{\Theta }}}$$ provides an alternative to n for measuring the extent of evolutionary change, and the mean clonal turnover time $${\overline{T}}_{{{\Theta }}}$$ indicates whether evolutionary change occurs mostly early or late during tumour growth (Methods). As expected, after an appropriate axis transformation, the pattern of clusters of D versus $$\overline{{{\Theta }}}$$ (Fig. 4b) resembles the pattern of clusters of D versus n (Fig. 3c). Plotting D versus a transformed $${\overline{T}}_{{{\Theta }}}$$ reveals a somewhat similar pattern, except that models with low $$\overline{{{\Theta }}}$$ exhibit high stochastic variation in $${\overline{T}}_{{{\Theta }}}$$ (Fig. 4c). Clonal turnover occurs relatively late in the non-spatial model but throughout tumour growth in the gland fission model. Given sufficient data, evolutionary modes can thus be described and classified in terms of various summary indices capturing distinct aspects of tumour evolution (for alternative diversity indices, see Extended Data Fig. 9).

### Influence of tumour architecture on mutation frequency distributions

As researchers and clinicians seldom have access to multi-regional sequencing data, or the longitudinal data needed to track how tumour clone sizes change over time, tumour phylogenies and evolutionary parameters are commonly inferred from mutation frequencies measured from a single biopsy sampled at a single time point. Moreover, current cancer sequencing technologies are neither sensitive enough to detect the majority of low-frequency mutations, nor precise enough to distinguish between high-frequency and clonal (100% frequency) mutations. Accordingly, the most relevant part of the mutation frequency distribution for practical purposes is in the intermediate frequency range. One way to examine differences between distributions within this intermediate range is to plot the cumulative mutation count (the number of mutations present at or above frequency f) versus the inverse mutation frequency (1/f). In a neutral non-spatial model, this graph is a straight line (Fig. 5a, blue points). Because the transformed mutation frequency distributions of many human cancers are also approximately linear, it has been proposed that neutral tumour evolution is widespread12. Deviations from this theoretical straight line have been taken as evidence of selection27,44.

Our population genetics modelling illustrates how not only selection but also tumour architecture has important effects on tumour mutation frequency distributions (Fig. 5 and Extended Data Fig. 10). In particular, when the cumulative mutation count is plotted against the inverse mutation frequency, the curve for the neutral model is no longer linear. Instead, for spatial models, the average non-neutral curve can be closer to a straight line than the average neutral model curve. These results confirm and extend previous findings27,35 indicating that methods using mutation frequencies to infer selection in solid tumours can yield incorrect conclusions if they fail to account for effects of population structure. Inappropriate choice of null model can therefore explain otherwise contradictory findings regarding the prevalence of neutral evolution in human cancers13,45.

## Discussion

In summary, we have found that differences in the range of cell–cell interactions and the manner of cell dispersal are sufficient to generate a spectrum of tumour evolutionary modes. This finding has important implications both for understanding tumour genomic data and for interpreting the results of previous computational models. Whereas mathematical oncologists have focused on mutation fitness effects5,12,27,44,46,47 or microenvironmental heterogeneity15, our perspective instead emphasizes the importance of population structure and gene flow in tumour evolution.

Prominent studies have variously used non-spatial models12,21,44,46, gland fission models5,27 or variants of the Eden growth model (in which cells compete with their nearest neighbours)32,47 to investigate aspects of tumour evolution (see Methods for further discussion of previous work). Our results imply that, at best, each of these model types is appropriate only in special cases. Accurate models of solid tumour evolution must faithfully recapitulate interactions within localized patches of cancer cells—the so-called tumour communities29—and between cancer cells and normal cells.

Consistent with previous work48, our models predict substantial variability in tumour evolutionary modes due to stochasticity in the timing, location and fitness effects of driver mutations. Our finding that this random variation approaches the variability observed within and between solid tumour types (Fig. 3b,c) suggests that it will be challenging to infer precise information about tumour structure and growth patterns from phylogenetic data, even given previous knowledge of mutation rates and fitness effects. Nevertheless, of the model types we have examined, we have shown that the most plausible for simulating evolution in the majority of malignant solid tumours, which exhibit branching evolution11, is the invasive glandular model introduced herein. A key feature of this model is that the speed at which a fitter clone spreads within its immediate ancestor is similar to the ancestor’s own expansion speed.

It follows from our findings that tumour architecture determines how well biopsy samples reflect intratumour heterogeneity. Oncologists typically base treatment decisions on the presence or absence of particular mutations in cells taken from only a small region of a solid tumour. Tumour types with structures that promote diversification are predicted to be the least responsive to targeted therapies, unless truncal mutations can be reliably identified and targeted.

Our framework also implies that a change in tumour architecture during cancer progression can lead to a change in the mode of tumour evolution. For example, the ‘big bang’ model of colorectal cancer4,5 posits that early selective sweeps are followed by effectively neutral evolution, such that mutation frequency is determined by the time of mutation occurrence. This idea was previously examined using a computational model of tumour growth via gland fission, with a maximum of one driver mutation per cell5. Based on more sophisticated population genetics modelling, we find reason to expect ongoing selection throughout the very early stages of colorectal tumour progression (when growth is driven by gland fission), enabling multiple driver mutations to reach high frequencies. In later stages, after cells from the adenoma invade neighbouring tissue and give rise to an adenocarcinoma, we predict a transition to either branching evolution or – because the invasion begins with numerous and/or highly transformed, rapidly expanding subclones49 – effectively neutral evolution. Punctuated evolution in colorectal tumours can thus be explained by the transition from gland fission to invasive growth. This explanation is broadly consistent with the big bang model and more recent multi-region sequencing studies6,49,50, while also agreeing with results of comparative genomic analysis, which indicate that colorectal cancers evolve subject to strong positive selection and have more driver mutations per cell than most other cancer types13,51. Transitions between evolutionary modes were recently investigated in a mathematical modelling study of ductal carcinoma,52 which complements the current work by likewise highlighting the importance of spatial competition.

In clear cell renal cell carcinoma, separate studies have found that tumour architecture53,54 and evolutionary trajectory9 are predictors of cancer progression and survival. Evolutionary mode correlates with both tumour architecture and clinical outcome in childhood cancers8,55. The manner of cell dispersal has prognostic value in colorectal and other solid cancers28. By mechanistically connecting tumour architecture to the mode of tumour evolution, our work provides a blueprint for a new generation of patient-specific models for forecasting tumour progression16,48 and for optimizing evolutionarily-informed treatment regimens56,57,58. This drive towards personalized models motivates further efforts to characterize how spatial structure interacts with other biological factors, such as spatially-varying carrying capacity29, alternative manners of cell dispersal19, immune interactions59, cancer stem cell hierarchies60, and frequency- or density-dependent cell fitness.17

## Methods

### Previous mathematical models of tumour population genetics

Many previous studies of tumour population genetics have used non-spatial branching processes21, in which cancer clones grow exponentially without interacting. Unless driver mutations increase cell fitness by less than 1%, these models predict lower clonal diversity and lower numbers of driver mutations than typically observed in solid tumours46. Among spatial models, a popular option is the Eden growth model (or boundary-growth model), in which cells are located on a regular grid with a maximum of one cell per site, and a cell can divide only if an unoccupied neighbouring site is available to receive the new daughter cell32,47,61. Other methods with one cell per site include the voter model32,62,63 (in which cells can invade neighbouring occupied sites) and the spatial branching process47 (in which cells budge each other to make space to divide). Further mathematical models have been designed to recapitulate glandular tumour structure by allowing each grid site or ‘deme’ to contain multiple cells and by simulating tumour growth via deme fission throughout the tumour5,26 or only at the tumour boundary27. A class of models in which cancer cells are organized into demes and disperse into empty space has also been proposed36,52,64. Supplementary Table 2 summarizes selected studies representing the state of the art of stochastic modelling of tumour population genetics.

Our main methodological innovations are to implement all these distinct model structures, and additional models of invasive tumours, within a common framework, and to combine them with methods for tracking driver and passenger mutations at single-cell resolution. The result is a highly flexible framework for modelling tumour population genetics that can be used to examine consequences of variation not only in mutation rates and selection coefficients, but also in spatial structure and manner of cell dispersal65.

### Computational model structure

Simulated tumours in our models are made up of patches of interacting cells located on a regular grid of sites. In keeping with the population genetics literature, we refer to these patches as demes. All demes within a model have the same carrying capacity, which can be set to any positive integer. Each cell belongs to both a deme and a genotype. If two cells belong to the same deme and the same genotype then they are identical in every respect, and hence the model state is recorded in terms of such subpopulations rather than in terms of individual cells. For the sake of simplicity, computational efficiency and mathematical tractability, we assume that cells within a deme form a well-mixed population. The well-mixed assumption is consistent with previous mathematical models of tumour evolution5,26,27,36,64 and with experimental evidence in the case of stem cells within colonic crypts66.

### Initial conditions

A simulation begins with a single tumour cell located in a deme at the centre of the grid. If the model is parameterized to include normal cells, then these are initially distributed throughout the grid such that each deme’s population size is equal to its carrying capacity. Otherwise, if normal cells are absent, then the demes surrounding the tumour are initially unoccupied.

### Stopping condition

The simulation stops when the number of tumour cells reaches a threshold value. Because we are interested only in tumours that reach a large size, if the tumour cell population succumbs to stochastic extinction, then results are discarded and the simulation is restarted (with a different seed for the pseudo-random number generator).

### Within-deme dynamics

Tumour cells undergo stochastic division, death, dispersal and mutation events, whereas normal cells undergo only division and death. The within-deme death rate is density-dependent. When the deme population size is less than or equal to the carrying capacity, the death rate takes a fixed value d0 that is less than the initial division rate. When the deme population size exceeds carrying capacity, the death rate takes a different fixed value d1 that is much greater than the largest attainable division rate. Hence, all genotypes grow approximately exponentially until the carrying capacity is attained, after which point the within-deme dynamics resemble a birth–death Moran process—a standard, well characterized model of population genetics.

In all spatially structured simulations, we set d0 = 0 to prevent demes from becoming empty. For the non-spatial (branching process) model, we set d0 > 0 and dispersal rate equal to zero, so that all cells always belong to a single deme (with carrying capacity greater than the maximum tumour population size).

### Mutation

When a cell divides, each daughter cell inherits its parent’s genotype plus a number of additional mutations drawn from a Poisson distribution. Each mutation is unique, consistent with the infinite-sites assumption of canonical population genetics models. Whereas some previous studies have examined the effects of only a single driver mutation (Supplementary Table 2), in our model there is no limit on the number of mutations a cell can acquire. Most mutations are passenger mutations with no phenotypic effect. The remainder are drivers, each of which increases the cell division or dispersal rate.

The programme records the immediate ancestor of each clone (defined in terms of driver mutations) and the matrix of Hamming distances between clones (that is, for each pair of clones, how many driver mutations are found in only one clone), which together allow us to reconstruct driver phylogenetic trees. To improve efficiency, the distance matrix excludes clones that failed to grow to more than ten cells and failed to produce any other clone before becoming extinct.

### Driver mutation effects

Whereas previous models have typically assumed that the effects of driver mutations combine multiplicatively, this can potentially result in implausible trait values (especially in the case of division rate if the rate of acquiring drivers scales with the division rate). To remain biologically realistic, our model invokes diminishing returns epistasis, such that the average effect of driver mutations on a trait value r decreases as r increases. Specifically, the effect of a driver is to multiply the trait value r by a factor of 1 + s(1 − r/m), where s > 0 is the mutation effect and m is an upper bound. Nevertheless, because we set m to be much larger than the initial value of r, the combined effect of drivers in all models in the current study is approximately multiplicative. For each mutation, the value of the selection coefficient s is drawn from an exponential distribution.

### Dispersal

Depending on model parameterization, dispersal occurs via either invasion or deme fission (Supplementary Table 3). In the case of invasion, the dispersal rate corresponds to the probability that a cell newly created by a division event will immediately attempt to invade a neighbouring deme. This particular formulation ensures consistency with a standard population genetics model known as the spatial Moran process. The destination deme is chosen uniformly at random from the four nearest neighbours (von Neumann neighbourhood). Invasion can be restricted to the tumour boundary, in which case the probability that a deme can be invaded is 1 − N/K if NK and 0 otherwise, where N is the number of tumour cells in the deme and K is the carrying capacity. If a cell fails in an invasion attempt, then it remains in its original deme. If invasion is not restricted to the tumour boundary, then invasion attempts are always successful.

In fission models, a deme can undergo fission only if its population size is greater than or equal to carrying capacity. As with invasion, deme fission immediately follows cell division (so that results for the different dispersal types are readily comparable). The probability that a deme will attempt fission is equal to the sum of the dispersal rates of its constituent cells (up to a maximum of 1). Deme fission involves moving half of the cells from the original deme into a new deme, which is placed beside the original deme. If the dividing deme contains an odd number of cells, then the split is necessarily unequal, in which case each deme has a 50% chance of receiving the larger share. Genotypes are redistributed between the two demes without bias according to a multinomial distribution. Cell division rate has only a minor effect on deme fission rate because a deme created by fission takes only a single cell generation to attain carrying capacity.

If fission is restricted to the tumour boundary, then the new deme’s assigned location is chosen uniformly at random from the four nearest neighbours, and if the assigned location already contains tumour cells, then the fission attempt fails. If fission is allowed throughout the tumour, then an angle is chosen uniformly at random, and demes are budged along a straight line at that angle to make space for the new deme beside the original deme.

Our particular method of cell dispersal was chosen to enable comparison between our results and those of previous studies and to facilitate mathematical analysis. In particular, when the deme carrying capacity is set to 1, our model approximates an Eden growth model (if fission is restricted to the tumour boundary, or if dispersal is restricted to the tumour boundary and normal cells are absent), a voter model (if invasion is allowed throughout the tumour) or a spatial branching process (if fission is allowed throughout).

To fairly compare different spatial structures and manners of cell dispersal, we set dispersal rates in each case such that the time taken for a tumour to grow from one cell to one million cells is approximately the same as in the neutral Eden growth model with maximal dispersal rate. This means that, across models, the cell dispersal rate decreases with increasing deme size. Given that tumour cell cycle times are on the order of a few days, the timespans of several hundred cell generations in our models realistically correspond to several years of tumour growth. More specifically, if we assume tumours take between 5 and 50 years to grow and the cell cycle time is between 1 and 10 days (both uniform priors), then the number of cell generations is between 400 and 8,000 in 95% of plausible cases. This order of magnitude is consistent with tumour ages inferred from molecular data67.

We note that, in addition to gland fission, gland fusion has been reported in normal human intestine68, which raises the possibility that gland fusion could occur during colorectal tumour development. However, the rate of crypt fission in tumours is much elevated relative to the rate in healthy tissue, and must exceed the rate of crypt fusion (or else the tumour would not grow). Therefore, even if crypt fusion occurs in human tumours, we do not expect it to have a substantial influence on evolutionary mode. This view is supported by previous computational modelling69.

### Two versus three dimensions

We chose to conduct our study in two dimensions for two main reasons. First, the effects of deme carrying capacity on evolutionary dynamics are qualitatively similar in two and three dimensions, yet a two-dimensional model is simpler, easier to analyse, and easier to visualize. Second, we aimed to create a method that is readily reproducible using modest computational resources and yet can represent the long-term evolution of a reasonably large tumour at single-cell resolution.

One million cells in two dimensions corresponds to a cross-section of a three-dimensional tumour with many more than one million cells. Therefore, compared to a three-dimensional model, a two-dimensional model can provide richer insight into how evolutionary dynamics change over a large number of cell generations. Developing an approximate, coarse-grained analogue of our model that can efficiently simulate the population dynamics of very large tumours with different spatial structures in three dimensions is an important direction for future research.

### Implementation

The programme implemented Gillespie’s exact stochastic simulation algorithm70 for statistically correct simulation of cell events. The order of event selection is (1) deme, (2) cell type (normal or tumour), (3) genotype, and (4) event type. At each stage, the probability of selecting an item (deme, cell type, genotype or event type) is proportional to the sum of event rates for that item, within the previous item. We measured elapsed time in terms of cell generations, where a generation is equal to the expected cell cycle time of the initial tumour cell.

### Sequencing data

We surveyed the multi-region and single-cell tumour sequencing literature to identify data sets suitable for comparison with our model results. Studies published before 2015 (for example, refs. 71,72,73,74) were excluded as they were found to have insufficient sequencing depth for our purposes. We also excluded studies that reconstructed phylogenies using samples from metastases or from multifocal tumours (for example, refs. 75,76,77,78,79,80) because our model is not designed to correspond to such scenarios. The seven studies we chose to include in our comparison are characterized by either high-coverage multi-region sequencing or large-sample single-cell sequencing of several tumours.

The ccRCC investigation81 we selected involved multi-region deep sequencing, targeting a panel of more than 100 putative driver genes. Three studies of NSCLC10, mesothelioma40 and breast cancer39 conducted multi-region whole-exome sequencing (first two studies) or whole-genome sequencing (latter study), and reported putative driver mutations. We also used data from single-cell RNA sequencing studies of uveal melanoma42 and breast cancer41, in which chromosome copy number variations were used to infer clonal structure, and a study of acute myeloid leukaemia (AML) that used single-cell DNA sequencing24. All seven studies constructed phylogenetic trees, which are readily comparable to the trees predicted by our modelling. The methodological diversity of these studies contributes to demonstrating the robustness of the patterns we seek to explain.

From each of the seven cohorts, we obtained data for between three and eight tumours. In the ccRCC data set, we focused on the five tumours for which driver frequencies were reported in the original publication. For NSCLC, we used data for the five tumours for which at least six multi-region samples were sequenced. In mesothelioma, we selected the six tumours that had at least five samples taken. From the breast cancer multi-region study, we used data for the three untreated tumours that were subjected to multi-region sequencing. From the single-cell sequencing studies of uveal melanoma and breast cancer, we used all the published data (eight tumours in each case), and from the AML study, we selected a random sample of eight tumours.

In multi-region sequencing data sets, it is uncertain whether all putative driver mutations were true drivers of tumour progression. One way to interpret the data (interpretation I1) is to assume that all putative driver mutations were true drivers that occurred independently. Alternatively, the more conservative interpretation I2 assumes that each mutational cluster (a distinct peak in the variant allele frequency distribution) corresponds to exactly one driver mutation, while all other mutations are hitchhikers. Thus, I1 permits linear chains of nodes that in I2 are combined into single nodes (compare Supplementary Figs. 9 and 10), and I1 leads to a higher estimate of the mean number of driver mutations per cell (our summary index n). If both the fraction of putative driver mutations that are not true drivers (false positives) and the fraction of true driver mutations that are not counted as such (false negatives) are low, or if these fractions approximately cancel out, then interpretation I1 will give a good approximation of n whereas I2 will give a lower bound. For the ccRCC, NSCLC and breast cancer cases in our data set, I1 generates values of n in the range 3–10 (mean 6.1), consistent with estimates based on other methodologies13,51, whereas for I2 the range is only 1–4 (mean 2.5). Accordingly, we used interpretation I1.

### Clonal diversity index

To measure clonal diversity, we used the inverse Simpson index defined as $$D=1/{\sum }_{i}{p}_{i}^{2}$$, where pi is the frequency of the ith combination of driver mutations. For example, if the population comprises k clones of equal size, then pi = 1/k for every value of i, and so D = 1/(k × 1/k2) = k. Clonal diversity has a lower bound D = 1. The inverse Simpson index is relatively robust to adding or removing rare types, which makes it appropriate for comparing data sets with differing sensitivity thresholds. Further examples are illustrated in Supplementary Fig. 11.

D is constrained by an upper bound for trees with n < 2, where n is the mean number of driver mutations per cell. Indeed, n = ∑iipi ≥ p1 + 2(1 − p1) = 2 − p1, so p1 ≥ 2 − n > 0, since n < 2. Therefore,

$$D=\frac{1}{{\sum }_{i}{p}_{i}^{2}}\le \frac{1}{{p}_{1}^{2}}\le \frac{1}{{(2-n)}^{2}}.$$

To see that this bound is tight, assume 1 ≤ n < 2 and consider a star-shaped tree with N nodes such that p1 = 2 − n and other nodes have equal weights pi = (1 − p1)/(N − 1) = (n − 1)/(N − 1) for i ≥ 2. The mean number of driver mutations per cell is p1 + 2(1 − p1) = 2 − p1 = n, and the inverse Simpson index is

$$\begin{array}{l}D=\frac{1}{\mathop{\sum }\nolimits_{i = 1}^{N}{p}_{i}^{2}}=\frac{1}{{p}_{1}^{2}+\mathop{\sum }\nolimits_{i = 2}^{N}{p}_{i}^{2}}\\=\frac{1}{{(2-n)}^{2}+(N-1){((n-1)/(N-1))}^{2}}=\frac{1}{{(2-n)}^{2}+{(n-1)}^{2}/(N-1)}.\end{array}$$

This quantity goes to 1/(2 − n)2 as the number of nodes N goes to infinity, so the bound 1/(2 − n)2 may be approached arbitrarily closely.

It is informative to derive the relationship between D and n for a population that evolves via a sequence of clonal sweeps, such that each new sweep begins only after the previous sweep is complete. For a given value of n, our simulations rarely produce trees with D values below the curves of this trajectory. Suppose that a population comprises a parent type and a daughter type, with frequencies p and 1 − p, respectively. If the daughter has m driver mutations, then the parent must have m − 1 driver mutations and n must satisfy m − 1 ≤ n ≤ m. More specifically,

$$n=(m-1)p+m(1-p)=m-p\ \Rightarrow \ p=m-n=1-\{n\},$$

where {n} denotes the fractional part of n (or 1 if n = m). The trajectory is therefore described by

$$D=\frac{1}{{p}^{2}+{(1-p)}^{2}}=\frac{1}{{(1-\{n\})}^{2}+{\{n\}}^{2}}.$$

We additionally calculated a curve representing the maximum possible diversity of linear trees. In the main text and below, we refer to this curve as corresponding to trees with an intermediate degree of branching. Specifically, this intermediate-branching curve is defined such that for every point below the curve (and with D > 1), there exist both linear trees and branching trees that have the corresponding values of n and D, whereas for every point above the curve there exist only branching trees. Derivation of the curve’s equation is provided in Supplementary Information. A first-order approximation (accurate within 1% for n ≥ 2.2) is D ≈ 9(2n − 1)/8.

To assess the extent to which clusters of points (n, D) are well separated, we calculated silhouette widths using the cluster R package82. A positive mean silhouette width indicates that clusters are distinct.

### Other diversity indices

Our diversity index fulfills the same purpose as the intratumour heterogeneity (ITH) index used in the TRACERx Renal study9, defined as the ratio of the number of subclonal driver mutations to the number of clonal driver mutations. However, compared to ITH, our index has the advantages of being a continuous variable and being robust to methodological differences that affect ability to detect low-frequency mutations. In calculating ITH from sequencing data, we included all putative driver mutations, whereas ref. 9 used only a subset of mutations. For model output, we classified mutations with frequency above 99% as clonal and we excluded mutations with frequency less than 1%. ITH and the inverse Simpson index are strongly correlated across our models (Spearman’s ρ = 0.98, or ρ = 0.81 for cases with D > 2; Extended Data Fig. 9c).

The Shannon index, defined as $${\sum }_{i}{p}_{i}{{\mathrm{log}}}\,{p}_{i}$$, is another alternative to the Simpson index. The exponential of this index has the same units as the inverse Simpson index (equivalent number of types). Compared to the Simpson index, the Shannon index gives more weight to rare types, which makes it somewhat less suitable for comparing data sets with differing sensitivity thresholds.

### Defining evolutionary modes in terms of indices D and n

In defining regions in terms of indices D and n (Table 1 and Fig. 3c), we first noted that if a population undergoes a succession of non-overlapping clonal sweeps, then at most two clones coexist at any time, and hence D ≤ 2. Allowing for some overlap between sweeps, we defined the ‘selective sweeps’ region as having D < 10/3 and D below the intermediate-branching curve. We put the upper boundary at D = 10/3 because this intersects with the intermediate-branching curve at n = 2.

We used D = 20 to define the boundary between the ‘branching’ and ‘progressive diversification’ regions. The TRACERx Renal study9 instead categorized trees containing more than 10 clones as highly branched, as opposed to branched. It is appropriate for us to use a higher threshold because our regions are based on true tumour diversity values, rather than the typically lower values inferred from multi-region sequencing data. Finally, we defined an ‘effectively almost neutral’ region containing star-shaped trees with n < 2 and D above the intermediate-branching curve.

It is possible to construct trees that do not fit the labels we have assigned to regions. For example (as shown in Supplementary Information), there exist linear trees within the branching and progressive diversification regions. Such exceptions are an unavoidable consequence of representing high-dimensional objects, such as phylogenetic trees, in terms of a small number of summary indices. Our labels are appropriate for the subset of trees that we have shown to arise from tumour evolution.

### Previously defined tree balance indices

Conventionally, the balance of a tree is the degree to which branching events split the tree into subtrees with the same number of leaves, or terminal nodes. A balanced tree thus indicates more equal extinction and speciation rates than an unbalanced tree83. Tree balance indices are commonly used to assert the correctness of tree reconstruction methods and to classify trees. We considered three previously defined indices, all of which are imbalance indices, which means that more balanced trees are assigned smaller values. We subtracted each of these indices from 1 to obtain measurements of tree balance.

Let T = (V, E) be a tree with a set of nodes V and edges E. Let V = N, and hence E = N − 1 (since each node has exactly one parent, except the root). We defined l as the number of leaves of the tree. The root is labelled 1 and the leaves are numbered from N − l + 1 to N. There is only one cladogram with two leaves, which is maximally balanced according to all the previously defined indices discussed below. We also considered the single-node tree to be maximally balanced with respect to these previously defined indices. The following definitions then apply when l ≥ 3.

For each leaf j, we defined νj as the number of interior nodes between j and the root, which is included in the count. Then a normalized version of Sackin’s index, originally introduced in ref. 84, is defined as

$${I}_{S,\mathrm{norm}}(T)=\frac{\mathop{\sum }\limits_{j=N-l+1}^{N}{\nu }_{j}-l}{\frac{1}{2}(l+2)(l-1)-l},$$

where to be able to compare indices of trees on different number of leaves l, we subtracted the minimal value for a given l and divided by the range of the index on all trees on n leaves, as in ref. 85.

For an interior node i of a binary tree T, we defined TL(i) as the number of leaves subtended by the left branch of Ti, the subtree rooted at i, and TR(i) the number of leaves subtended by its right branch. Then, the unnormalized Colless index86 of T is

$${I}_{C}(T)=\mathop{\sum }\limits_{i=1}^{N-l}| {T}_{L}(i)-{T}_{R}(i)| .$$

Since Colless index is defined only for bifurcating trees, we used the default normalized Colless-like index $${{\mathfrak{C}}}_{{\mathrm{MDM}},\,{{\mathrm{ln}}}(l+e),\,{\mathrm{norm}}}$$ defined in ref. 85. This consisted of measuring the dissimilarity between the subtrees $$T^{\prime}$$ rooted at a given internal node by computing the mean deviation from the median (MDM) of the f-sizes of these subtrees. In this case, $$f(l)={{\mathrm{ln}}}(l+e)$$ and the f-size of $$T^{\prime}$$ is defined as

$$\mathop{\sum}\limits_{v\in V(T^{\prime} )}{\mathrm{ln}}({\mbox{deg}}(v)+e).$$

These dissimilarities were then summed and the result was normalized as for Sackin’s index.

The cophenetic value ϕ(i, j) of a pair of leaves i, j is the depth of their lowest common ancestor (such that the root has depth 0). The total cophenetic index87 of T is then the sum of the cophenetic values over all pairs of leaves, and a normalized version is

$${I}_{{{\Phi }},{\mathrm{norm}}}(T)=\frac{\mathop{\sum}\limits_{N-l+1\le i < j\le N}\phi (i,j)}{\left({l}\atop{3}\right)},$$

where here the minimal value of the cophenetic index is 0 for all l (for a star-shaped tree with l leaves).

These three balance indices were designed for analysing species phylogenies and are thus defined on cladograms, which are trees in which leaves correspond to extant species and internal nodes are hypothetical common ancestors. Conventional cladograms have no notion of node size. Cladograms also lack linear components as each internal node necessarily corresponds to a branching event. The driver phylogenetic trees reported in multi-region sequencing studies and generated by our models are instead clone trees (also known as mutation trees), in which all nodes of non-zero size represent extant clones. To apply previous balance indices to driver phylogenetic trees, we first converted the trees to cladograms by adding a leaf to each non-zero-sized internal node and collapsing linear chains of zero-sized nodes.

Whereas diversity indices such as D are relatively robust to the addition or removal of rare clones, the balance indices described above are much less robust because they treat all clones equally, regardless of population size (Supplementary Figs. 6, 7 and 8). This hampered comparison between model results and data for two reasons. First, due to sampling error, even high quality multi-region sequencing studies underestimate the number of subclonal, locally abundant driver mutations by approximately 25%81. Second, bulk sequencing cannot detect driver mutations present in only a very small fraction of cells.

### A robust tree balance index

To overcome the shortcomings of previous indices, we have developed a more robust tree balance index based on an extended definition: tree balance is the degree to which internal nodes split the tree into subtrees of equal size, where size refers to the sum of all node populations.

Let f(v) > 0 denote the size of node v. For an internal node i, let V(Ti) denote the set of nodes of Ti, the subtree rooted at i. We then define

$$\begin{array}{l}{S}_{i}=\mathop{\sum}\limits_{v\in V({T}_{i})}f(v)=\,{{\mathrm{the}}\ {\mathrm{size}}\ {\mathrm{of}}}\,\,{T}_{i},\\ {S}_{i}^{* }=\mathop{\sum}\limits_{v\in V({T}_{i})\atop {v\ne i}}f(v)=\,{{\mathrm{the}}\ {\mathrm{size}}\ {\mathrm{of}}}\,\,{T}_{i}\,\,{{\mathrm{without}}\ {\mathrm{its}}\ {\mathrm{root}}}\,\,i.\end{array}$$

For i in the set of internal nodes $$\widetilde{V}$$, and j in the set C(i) of children of i, we define $${p}_{ij}={S}_{j}/{S}_{i}^{* }$$. We then computed the balance score $${W}_{i}^{1}$$ of a node $$i\in \widetilde{V}$$ as the normalized Shannon entropy of the sizes of the subtrees rooted at the children of i:

$${W}_{i}^{1}=\mathop{\sum}\limits_{j\in C(i)}{W}_{ij}^{1},\quad \,{{\mbox{with}}}\,{W}_{ij}^{1}=\left\{\begin{array}{ll}-{p}_{ij}{{{\mathrm{log}}}\,}_{{d}^{+}(i)}{p}_{ij}&\,{{\mbox{if}}}\,\,{p}_{ij} > 0\,{{\mbox{and}}}\,\,{d}^{+}(i)\ge 2,\\ 0&\,{{\mbox{otherwise,}}}\,\end{array}\right.$$

where d+(i) is the out-degree (the number of children) of node i. Finally, for each node i, we weighted the balance score by the product of $${S}_{i}^{* }$$ and a non-root dominance factor $${S}_{i}^{* }/{S}_{i}.$$ Our normalized balance index is then

$${J}^{1}:= \frac{1}{{\sum }_{k\in \widetilde{V}}{S}_{k}^{* }}\mathop{\sum}\limits_{i\in \widetilde{V}}{S}_{i}^{* }\frac{{S}_{i}^{* }}{{S}_{i}}{W}_{i}^{1}.$$

Supplementary Fig. 11 illustrates the calculation of J1 for four exemplary trees. We further describe the desirable properties of this index, and its relationship to other tree balance indices, in another article43.

When n ≤ 2 (where n is the mean number of driver mutations per cell), the non-root dominance factor cannot exceed n − 1, while the other factors in J1 are at most 1, which implies J1 ≤ n − 1 for all n ≤ 2. Also for n > 2, we have J1 ≤ 1 < n − 1. Thus, it is impossible to construct trees that have J1 > n − 1, as shown in Fig. 4a.

### Clonal turnover indices

For each time point t ≥ δt, we defined a clonal turnover index as

$${{\Theta }}(t)=\mathop{\sum}\limits_{i}{\left({f}_{i}(t)-{f}_{i}(t-\tau )\right)}^{2},$$

where fi(t) is the frequency of clone i at time t, and τ is 10% of the total simulation time measured in cell generations. The mean value $$\overline{{{\Theta }}}$$ over time measures the total extent of clonal turnover.

To determine whether clonal turnover mostly occurred early, late or throughout tumour evolution, we calculated the weighted average

$${\overline{T}}_{{{\Theta }}}=\frac{1}{\max (t)}\left(\mathop{\sum}\limits_{t}{{\Theta }}(t)t\bigg/\mathop{\sum}\limits_{t}{{\Theta }}(t)\right),$$

where $$\max (t)$$ denotes the final time of the simulation. This quantity takes values between 0 and 1, and is higher if clonal turnover occurs mostly late during tumour growth. If the rate of clonal turnover is constant over time, then $${\overline{T}}_{{{\Theta }}}\approx 0.55$$.

### Histology slide analysis to determine the number of cells per gland

We randomly selected five tumours of each of four cancer types (colorectal cancer, clear cell renal cancer, lung adenocarcinoma and breast cancer) from The Cancer Genome Atlas (TCGA) reference database (http://portal.gdc.cancer.gov). Using QuPath v0.2.0m488, we manually delineated five representative groups of tumour cells in each image and automatically counted the number of cells in each group. We defined a group as a set of tumour cells directly touching each other, separated from other groups by stroma or other non-tumour tissue (Extended Data Fig. 3).

The number of cells per group ranged from 5 to 8,485, with 50% of cases having between 53 and 387 cells (Extended Data Fig. 4a). Variation in the number of cells per group was larger between rather than within tumours, whereas cell density was relatively consistent between tumours (Extended Data Fig. 4b). Because our cell counts were derived from cross sections, they would underestimate the true populations of three-dimensional glands. On the other hand, it is unknown what proportion of cells are able to self-renew and contribute to long-term tumour growth and evolution89. On balance, therefore, it is reasonable to assume that each gland of an invasive glandular tumour can contain between a few hundred and a few thousand interacting cells. This range of values is, moreover, remarkably consistent with results of a recent study that used a very different method to infer the number of cells in tumour-originating niches. Across a range of tissue types, this study concluded that cells typically interact in communities of 300–1,900 cells30. Another recent study of breast cancer applied the Louvain method for community detection to identify two-dimensional tumour communities typically in the range of 10–100 cells.29

### Reporting Summary

Further information on research design is available in the Nature Research Reporting Summary linked to this article.


text:
# hicBuildMatrix¶

Using an alignment from a program that supports local alignment (eg. Bowtie2) where both PE reads are mapped using the –local option, this program reads such file and creates a matrix of interactions.

usage: hicBuildMatrix --samFiles two sam files two sam files --outFileName
FILENAME --QCfolder FOLDER --restrictionCutFile BED file
[BED file ...] --restrictionSequence RESTRICTIONSEQUENCE
[RESTRICTIONSEQUENCE ...] --danglingSequence
DANGLINGSEQUENCE [DANGLINGSEQUENCE ...]
[--outBam bam file] [--binSize BINSIZE [BINSIZE ...]]
[--minDistance MINDISTANCE] [--maxDistance MAXDISTANCE]
[--maxLibraryInsertSize MAXLIBRARYINSERTSIZE]
[--genomeAssembly GENOMEASSEMBLY]
[--region CHR:START-END]
[--removeSelfLigation REMOVESELFLIGATION]
[--keepSelfCircles]
[--minMappingQuality MINMAPPINGQUALITY]
[--doTestRun] [--doTestRunLines DOTESTRUNLINES]
[--skipDuplicationCheck] [--chromosomeSizes txt file]
[--help] [--version]

## Required arguments¶

--samFiles, -s

The two PE alignment sam files to process

--outFileName, -o

Output file name for the Hi-C matrix.

--QCfolder

Path of folder to save the quality control data for the matrix. The log files produced this way can be loaded into hicQC in order to compare the quality of multiple Hi-C libraries.

--restrictionCutFile, -rs

BED file(s) with all restriction cut sites (output of “hicFindRestSite” command). Should only contain the restriction sites of the same genome which has been used to generate the input sam files. Using regions of a different genome version can generate false results! To use more than one restriction enzyme, generate a restrictionCutFile for each enzyne and list them space seperated.

--restrictionSequence, -seq

Sequence of the restriction site, if multiple are used, please list them space seperated. If a dangling sequence is listed at the same time, please preserve the same order.

--danglingSequence

Sequence left by the restriction enzyme after cutting, if multiple are used, please list them space seperated and preserve the order. Each restriction enzyme recognizes a different DNA sequence and, after cutting, they leave behind a specific “sticky” end or dangling end sequence. For example, for HindIII the restriction site is AAGCTT and the dangling end is AGCT. For DpnII, the restriction site and dangling end sequence are the same: GATC. This information is easily found on the description of the restriction enzyme. The dangling sequence is used to classify and report reads whose 5’ end starts with such sequence as dangling-end reads. A significant portion of dangling-end reads in a sample are indicative of a problem with the re-ligation step of the protocol.

## Optional arguments¶

--outBam, -b

Output bam file to process. Optional parameter. A bam file containing all valid Hi-C reads can be created using this option. This bam file could be useful to inspect the distribution of valid Hi-C reads pairs or for other downstream analyses, but is not used by any HiCExplorer tool. Computation will be significantly longer if this option is set.

--binSize, -bs

Size in bp for the bins. The bin size depends on the depth of sequencing. Use a larger bin size for libraries sequenced with lower depth. If not given, matrices of restriction site resolution will be built. Optionally for mcool file format: Define multiple resolutions which are all a multiple of the first value. Example: –binSize 10000 20000 50000 will create a mcool file formate containing the three defined resolutions.

--minDistance

Minimum distance between restriction sites. Restriction sites that are closer than this distance are merged into one. This option only applies if –restrictionCutFile is given (Default: 300).

Default: 300

--maxDistance

This parameter is now obsolete. Use –maxLibraryInsertSize instead

--maxLibraryInsertSize

The maximum library insert size defines different cut offs based on the maximum expected library size. This is not the average fragment size but the higher end of the the fragment size distribution (obtained using for example a Fragment Analyzer or a Bioanalyzer) which usually is between 800 to 1500 bp. If this value is not known use the default value. The insert value is used to decide if two mates belong to the same fragment (by checking if they are within this max insert size) and to decide if a mate is too far away from the nearest restriction site (Default: 1000).

Default: 1000

--genomeAssembly, -ga

The genome the reads were mapped to. Used for metadata of cool file.

--region, -r

Region of the genome to limit the operation to. The format is chr:start-end. It is also possible to just specify a chromosome, for example –region chr10

--removeSelfLigation

If set, inward facing reads less than 1000 bp apart and having a restrictionsite in between are removed. Although this reads do not contribute to any distant contact, they are useful to account for bias in the data (for the moment is always True).

Default: True

--keepSelfCircles

If set, outward facing reads without any restriction fragment (self circles) are kept. They will be counted and shown in the QC plots.

Default: False

--minMappingQuality

minimum mapping quality for reads to be accepted. Because the restriction enzyme site could be located on top of the read, this may reduce the reported quality of the read. Thus, this parameter may be adjusted if too many low quality (but otherwise perfectly valid Hi-C reads) are found. A good strategy is to make a test run (using the –doTestRun), then checking the results to see if too many low quality reads are present and then using the bam file generated to check if those low quality reads are caused by the read not being mapped entirely (Default: 15).

Default: 15

Default: 4

--inputBufferSize

Size of the input buffer of each thread. 400,000 read pairs per input file per thread is the default value. Reduce this value to decrease memory usage.

Default: 400000

--doTestRun

A test run is useful to test the quality of a Hi-C experiment quickly. It works by testing only 1,000,000 reads. This option is useful to get an idea of quality control values like inter-chromosomal interactions, duplication rates etc.

Default: False

--doTestRunLines

Number of lines to consider for the qc test run (Default: 1000000).

Default: 1000000

--skipDuplicationCheck

Identification of duplicated read pairs is memory consuming. Thus, in case of memory errors this check can be skipped. However, consider running a –doTestRun first to get an estimation of the duplicated reads.

Default: False

--chromosomeSizes, -cs

File with the chromosome sizes for your genome. A tab-delimited two column layout “chr_name size” is expectedUsually the sizes can be determined from the SAM/BAM input files, however, for cHi-C or scHi-C it can be that at the start or end no data is present. Please consider that this option causes that only reads are considered which are on the listed chromosomes.Use this option to guarantee fixed sizes. An example file is available via UCSC: http://hgdownload.soe.ucsc.edu/goldenPath/dm3/bigZips/dm3.chrom.sizes

--version

show program’s version number and exit

Please note that the file type extension for the output matrix (--outFileName) must be given! This can be .h5, .cool or the specializations of cool .mcool, if the path is given! For .scool files please create one .cool file per cell and merge it together with scHiCExplorer’s scHicMergeToSCool.

## Building multicooler matrices¶

hicBuildMatrix supports building multicooler matrices which are for example needed for visualization with HiGlass. To do so, use as out file format either .cool or .mcool and define the desired resolutions as –binSize. hicBuildMatrix builds the interaction matrix for the highest resolution and merges the bins for the lower resolutions. The lower resolutions need to be an integer multiplicative of the highest resolution.

\$ hicBuildMatrix -s forward.bam reverse.bam -o multi_resolution.cool
--binSize 10000 20000 50000 100000 --QCfolder QC

Introducing with version 3.5 we support multiple restriction and dangling end sequences, and multiple restriction cut site files. Hi-C protocols that use multiple restriction cut enzymes benefit from this and get now an improved QC report. Version 3.5 adds also the support for a chromosome size file which can help to get interaction matrices with a predefined size. Capture Hi-C or single-cell Hi-C data, where it is not guaranteed that reads from all areas of the chromosome are present benefit from this latest improvement.

## Missing scaffolds or contigs in the Hi-C matrix¶

Restriction enzymes cut the DNA at their specific restriction cut site sequences. It can occur for scaffolds or contigs (less likely it happens for chromosomes) that it does not contain any of these cut sites. In this case, the reads from this scaffold or contig are considered as invalid and are part of the ‘same restriction fragment’-statistics in the QC report.

format: plain


text:
ï»¿ Factor Formula - the sum of sine of two angles

# Factor Formula - the sum of sine of two angles

hchj

The sum of sine of two angles is equal to the double of the product of sine of average of the two angles and cosine of half of the difference of the two angles.

\sin \alpha + \sin \beta = 2\sin\dfrac{\alpha +\beta }{2} \cos\dfrac{\alpha -\beta }{2}

or

Scroll to Top


text:
Select Page

Question:

Let $$A(\theta)=\begin{pmatrix} cos(\theta) & sin(\theta) \\ -sin(\theta) & cos(\theta) \end{pmatrix}$$

where $$\theta \in (0,2\pi)$$. Mark the correct statement below:

A. $$A(\theta)$$ has eigenvectors in $$\mathbb{R}^2$$ for all $$\theta \in (0,2\pi)$$

B.  $$A(\theta)$$ does not have eigenvectors in $$\mathbb{R}^2$$ for any $$\theta \in (0,2\pi)$$

C.  $$A(\theta)$$ has eigenvectors in $$\mathbb{R}^2$$ for exactly one values of  $$\theta \in (0,2\pi)$$

D. $$A(\theta)$$ has eigenvectors in $$\mathbb{R}^2$$ for exactly 2 values of $$\theta \in (0,2\pi)$$

Discussion:

If we try to write the linear operator on $$\mathbb{R}^2$$ which is the clockwise rotation by angle $$\theta$$ then we see that with respect to standard basis, the matrix is $$A(\theta)$$. This is quite easy to see, for $$(1,0) \to (cos(\theta),-sin(\theta))$$, and $$…$$ (draw the picture if you are not convinced about this).

What does having an eigenvector mean in this context? Well, as always, it means that $$Av=\lambda v$$ for some $$v \neq 0$$ in $$\mathbb{R}^2$$. But geometrically, this means that upon applying the transformation (in this case rotation) we get the resulting vector in the spanning space of $$v$$, that is the resulting vector must be in the line passing through $$v$$ and the origin.

Geometrically, after rotation, the vector is in the same line is possible only when either the angle of rotation is $$0$$ or the angle of rotation is $$\pi$$. That is either we did not move at all or we basically reflected about origin.

$$\theta \neq 0$$, so we are left with $$\theta=\pi$$. Therefore, we know option C is true.

If you do not trust your geometric sense at all, then you would want to look at the characteristic polynomial.

We have $$det(A(\theta))=cos^2(\theta)+sin^2(\theta)=1$$ and $$trace(A(\theta))=2cos(\theta)$$.

Therefore, the characteristic polynomial is $$x^2-2cos(\theta)x+1$$. This has a real root if the discriminant is positive. That is if $$4cos^2(\theta)-4 \ge 0$$ i.e, $$cos^2(\theta) \ge 1$$. We know that the maximum value of cos is 1 so $$cos(\theta)=1$$ or $$cos(\theta)=-1$$. Since $$\theta \ne 0$$ we are forced to conclude $$\theta = \pi$$ and we have the answer once more.


text:
# Subgroups of Order Three

[SOLVED] Subgroups of Order Three

Homework Statement
Let G be a subgroup containing exactly eight elements of order three. How many subgroups of order three does G have?

The attempt at a solution
This problem was discussed in class today. The professor said that G has four subgroups of order three. I didn't follow his explanation very well so I didn't understand why. Since there are eight elements of order three, wouldn't each of these elements constitute a subgroup of order three so G has at least eight subgroups of order three?

Suppose $$a \in G$$ is order 3 then $$a^2$$ is also order 3. They belong to the same subgroup. That means that only 4 of the 8 are generators, and the other 4 are their squares.


text:
Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

A. Sum of Odd Integers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers $n$ and $k$. Your task is to find if $n$ can be represented as a sum of $k$ distinct positive odd (not divisible by $2$) integers or not.

You have to answer $t$ independent test cases.

Input

The first line of the input contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

The next $t$ lines describe test cases. The only line of the test case contains two integers $n$ and $k$ ($1 \le n, k \le 10^7$).

Output

For each test case, print the answer — "YES" (without quotes) if $n$ can be represented as a sum of $k$ distinct positive odd (not divisible by $2$) integers and "NO" otherwise.

Example
Input
6
3 1
4 2
10 3
10 2
16 4
16 5

Output
YES
YES
NO
YES
YES
NO

Note

In the first test case, you can represent $3$ as $3$.

In the second test case, the only way to represent $4$ is $1+3$.

In the third test case, you cannot represent $10$ as the sum of three distinct positive odd integers.

In the fourth test case, you can represent $10$ as $3+7$, for example.

In the fifth test case, you can represent $16$ as $1+3+5+7$.

In the sixth test case, you cannot represent $16$ as the sum of five distinct positive odd integers.


text:
# American Institute of Mathematical Sciences

• Previous Article
Explicit Jenkins-Strebel representatives of all strata of Abelian and quadratic differentials
• JMD Home
• This Issue
• Next Article
On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method
January  2008, 2(1): 129-138. doi: 10.3934/jmd.2008.2.129

## Simultaneous diophantine approximation with quadratic and linear forms

 1 School of Mathematics, Tata Institute of Fundamental Research, Homi Bhabha Road, Colaba, Mumbai 400 005, India

Received  August 2007 Revised  October 2007 Published  October 2007

Let $Q$ be a nondegenerate indefinite quadratic form on $\mathbb{R}^n$, $n\geq 3$, which is not a scalar multiple of a rational quadratic form, and let $C_Q=\{v\in \mathbb R^n | Q(v)=0\}$. We show that given $v_1\in C_Q$, for almost all $v\in C_Q \setminus \mathbb R v_1$ the following holds: for any $a\in \mathbb R$, any affine plane $P$ parallel to the plane of $v_1$ and $v$, and $\epsilon >0$ there exist primitive integral $n$-tuples $x$ within $\epsilon$ distance of $P$ for which $|Q(x)-a|<\epsilon$. An analogous result is also proved for almost all lines on $C_Q$.
Citation: Shrikrishna G. Dani. Simultaneous diophantine approximation with quadratic and linear forms. Journal of Modern Dynamics, 2008, 2 (1) : 129-138. doi: 10.3934/jmd.2008.2.129
 [1] Federico Rodriguez Hertz, Zhiren Wang. On $\epsilon$-escaping trajectories in homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 329-357. doi: 10.3934/dcds.2020365 [2] Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374 [3] Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 [4] Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463 [5] Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169 [6] Bo Chen, Youde Wang. Global weak solutions for Landau-Lifshitz flows and heat flows associated to micromagnetic energy functional. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020268 [7] Helmut Abels, Andreas Marquardt. On a linearized Mullins-Sekerka/Stokes system for two-phase flows. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020467 [8] Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015 [9] Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250 [10] Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049 [11] Mingjun Zhou, Jingxue Yin. Continuous subsonic-sonic flows in a two-dimensional semi-infinitely long nozzle. Electronic Research Archive, , () : -. doi: 10.3934/era.2020122 [12] Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

2019 Impact Factor: 0.465


text:
## Doctoral Dissertations

#### Title

The effects of acetate and selected inhibitors on the phenotypic and metabolic traits of {\it Cytophaga johnsonae\/}

January 1997

#### Keywords

Biology, Microbiology

Ph.D.

#### Abstract

Cytophaga johnsonae belongs to a group of microorganisms known as the gliding bacteria. Characteristically, cells of these bacteria are able to translocate across solid surfaces but are unable to swim through liquids. Their motility is unusual in that it does not arise from detectable organelles, such as flagella, and the mechanism(s) for this motility is unknown. Since these species must make contact with solid surfaces to move, their cell envelope must play an indispensable role in translocation. The membrane of C. johnsonae contains high levels of branched-chain fatty acids, which is unusual for Gram-negative organisms. To ascertain the role that these lipids play in gliding motility, biochemical features of the cell envelope were studied by growing cells with acetate in an attempt to alter their lipid composition. Although cells grown with acetate did not demonstrate any significant differences in the cellular fatty acids, sulfonolipid synthesis did show a proportionate decrease in the presence of acetate.^ Polystyrene latex bead movement on the cell surface is considered by some to be a manifestation of the gliding machinery; however, this relationship has been questioned by others due to contradictory observations. Growth in acetate stopped the movement of beads on the cell surface, while gliding motility was unaffected. The results of this study confirm that bead movement on the cell surface is not a prerequisite for or equivalent to the phenomenon of gliding motility.^ Since acetate is a weak acid, it may act as an uncoupler of oxidative phosphorylation, and thereby decrease the energy supply of the cell. The protonmotive force has been considered to be the source of energy for gliding motility (and presumably, bead movement), and if the electrochemical gradient of the membrane were diminished, the ability of cells to glide could be affected. Intracellular ATP, respiratory activity, and protonmotive force were assessed in cells grown with acetate, as well as select inhibitors of energy-related functions. It was found that ATP and/or O$\sb2$ consumption of the cell could be dramatically decreased without appreciably affecting the protonmotive force. In addition, gliding motility does not depend upon the energy derived from ATP, whereas, bead movement on the cell surface may be influenced by ATP levels. ^

COinS


text:
Click To Get Off-Campus Placement Jobs Info !!!

# C Programming :: Basic Concepts

NA
SHSTTON
0
Solv. Corr.
10
Solv. In. Corr.
10
Attempted
0 M:0 S
Avg. Time

51 / 90

Choose the correct option.

What would be the value assigned to a,b and c if the statement scanf ("%3d,%3d,%3d", &a,&b,&c) is executed with input data as 1234_5678_9 (Note: _ denote as blank)

Aa=123,b=4,c=567

Ba=123,b=567,c=9

Ca=123,b=456,c=789

Da=1234,b=5678,c=9

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
3
Solv. Corr.
9
Solv. In. Corr.
12
Attempted
0 M:0 S
Avg. Time

52 / 90

What will be the output of the following C program?
void main()
{
int i= 1234; j = 0177, k = 0xa08c;
printf ("%8d %80x /n", I,j,k),
}

A12341777 a08c

B12341 abc a08c

C00001234 01aa ax

D12340777 ao80

Explanation:

The output will be an error, since variables 'j' and 'k' are not declared.

Workspace

NA
SHSTTON
0
Solv. Corr.
10
Solv. In. Corr.
10
Attempted
0 M:0 S
Avg. Time

53 / 90

Choose the correct option.

The conditional compilation

AIt is taken care of by the compiler

BIt is setting the compiler option conditionally

CIt is compiling a program based on a condition

Dnone of above

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
1
Solv. Corr.
10
Solv. In. Corr.
11
Attempted
0 M:0 S
Avg. Time

54 / 90

Choose the correct option.

Originally 'C' was developed as:

ASystem programming language

BGeneral purpose language

CData processing language

DNone of above

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
1
Solv. Corr.
10
Solv. In. Corr.
11
Attempted
0 M:0 S
Avg. Time

55 / 90

Choose the correct option.

Latency time is:

ATime taken by read/write head mechanism to position itself over appropriate cylinder

BTime taken to transfer a dta from memory

DNone of above

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
1
Solv. Corr.
10
Solv. In. Corr.
11
Attempted
0 M:0 S
Avg. Time

56 / 90

Choose the correct option.

The two types of file structure existing in VSAM file are

AKey sequenced structure, entry sequenced structure

BKey sequence structure, exit sequenced structure

CEntry sequence structure, exit sequenced structure

DNone of above

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
2
Solv. Corr.
9
Solv. In. Corr.
11
Attempted
0 M:0 S
Avg. Time

57 / 90

Choose the correct option.

In C language, a hexadecimal number is represented by writing

Ax

Bx0

C0x

Dh

Explanation:

Hexadecimal numbers in C are represented by 0x or 0X.

For example: the value in Hexadecimal can be written as 0x64, which is equivalent to 100 in decimal.

Hence, the correct option is C.

Workspace

NA
SHSTTON
2
Solv. Corr.
12
Solv. In. Corr.
14
Attempted
0 M:0 S
Avg. Time

58 / 90

Choose the correct option.

In which of the cases, the content inside if statement will not execute

Aif(-100)

Bif(0)

Cif (23.45)

DAll of the above

Explanation:

Option A and C will execute as both -100 and 23.45 are not equal to 0, so the test condition becomes True, hence the contect inside if statement will execute.

Whereas, option B will not execute as 0 not equal to 0 is False, so the content inside if statement won't execute.

Therefore, correct option is B

Workspace

NA
SHSTTON
7
Solv. Corr.
3
Solv. In. Corr.
10
Attempted
0 M:2 S
Avg. Time

59 / 90

Choose the correct option.

AReallocation

BAllocation

DBoth (a) and (b)

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
6
Solv. Corr.
26
Solv. In. Corr.
32
Attempted
0 M:0 S
Avg. Time

60 / 90

Choose the correct option.

What is the sizeof(long int)

A4 bytes

B2 bytes

CCompiler dependent

D8 bytes

Explanation:

The size for long int depends on the compiler. For a 32-bit model, the size is 4 bytes, whereas for a 64-bit model the size is 8 bytes

Hence, the correct option is C.

Workspace

## C Programming Basic Concepts Questions and Answers pdf

At C Programming topic Basic Concepts, you will get multiple online quiz difficulty wise, which will have a total of 6 quizzes, categorized as easy, medium, and moderate level. While preparing for any Basic Concepts, take all the list quiz and check your preparation level for that topic. Each quiz have 10 different question, which needs to be answered in 20 min., all the listed quiz here is free, however, you will get only one chance for each quiz to attempt(Take Quiz seriously), so it is always recommended to take one quiz in each section before you start solving Basic Concepts MCQs practice question, and one after solving all the question of the respective level, you can refer back your Basic Concepts quiz result any time or you can download it as pdf for reference.

## C Programming Basic Concepts Customize Online Mock Test

This is own type of mock test, where At this C Programming Basic Concepts MCQs mock test section, you will able to attempt only the questions related to Basic Concepts, in that question will be a different level, important, and all the questions will be part of some of the mock tests across Q4interview FREE Mock test. You need to choose the topic as Basic Concepts, and click on Double click to generate your customize mock test. While attempting the mock test you need to choose any of the one options out of given option. It is recommended to go through the direction given along with each question, as these questions will be randomly and so that same direction will not be applicable across the entire test. Once you submit your mock test, the result will be generated for Basic Concepts Customize mock test, where your performance point points will be highlighted. Q4interview analysis every single point which helps you to improve your topic understanding and help you to know your type of mistakes and way to improve Basic Concepts questions, by providing the same type of practice questions from practice exercise. The best part of this Basic Concepts, all these mock tests listed here are free and you can take as Many time, as many you want. When you continue to give Basic Concepts Customize Online Mock Test here regularly, then you will understand how much you have developed your accuracy on a topic, after that you will be able to decide how much attention you need to focus on. Your continued practice will increase your confidence, speed and thinking ability intensely, the Basic Concepts Customize topic on which you will practice more will beneficial for you in future during campus placement.

## C Programming Basic Concepts Quiz Online Test

The details of the C Programming Basic Concepts quiz are as follows. There are 10 questions for you. You have to answer them in 20 minutes. Within 20 minutes you have to see the errors in the sentences given as a question. Four options are also given to you, and you have to choose your opinion. You must be confident in your answer that the choices are difficult. Therefore, below we provide you with some information about C Programming Basic Concepts that you see and keep them in mind while answering questions.

## C Programming Basic Concepts MCQs Practice Questions with Answer

On this Basic Concepts section of page you will find the easiest quickest ways to solve a question, formulas, shortcuts and tips and tricks to solve various easiest methods to solve Basic Concepts Question Quickly. It contains all the C Programming topic Basic Concepts questions which are common in any of the preliminary exams of any company. The solution is provided along with the questions. The practice of these questions is a must as they are easy as well as scoring and asked in all the exams They will confirm the selection if all the questions attempted wisely with little practice. It is recommanded to Take Mock test based on C Programming topic and Basic Concepts topic based quiz.

## C Programming Basic Concepts solved examples question

Clarity of concepts is a must if you want to master the skill of solving C Programming problems. This page contains sample C Programming Basic Concepts questions and answers for freshers and competitive exams. Basic Concepts Questions with the detailed description, the explanation will help you to master the topic. Here solved examples with detailed answer description, explanations are given and it would be easy to understand. How to solve qBasic ConceptsC Programming? Here are some examples solved with the Common Rules/tricks/tips of C Programming. Enhance your chance to score maximum marks in C Programming sections through. Error Spotting Grammar Questions Online Test for Free. Fully solved Sentence Formation MCQs questions with detailed answer description. C Programming is an important topic for any exams but most aspirants find it difficult. You need to learn various tricks tips, rules, etc to solve quickly. At this page, you will find frequently asked Basic Concepts questions or problems with solutions, shortcuts, formulas for all-important competitive exams like IT companies exams, interviews. It is always a best practice to go through the example and understand the types of question and way to solve it, so let's do some examples to calculate efficiency, read through all the given here solved examples. You can post your solution, tips, trick and shortcut if you have any in respect to questions.

You can get here fully solved Basic Concepts examples with a detailed answer and description. You can solve Basic Concepts problems with solutions, the questions by companies wise by filtering the questions, additionally, you can check what type of questions are being asked in IT companies Written Round from Basic Concepts. Basic Concepts became one of the most important sections in the entire competitive exams, Companies Campus, and entrance online test. Go through Basic Concepts Examples, Basic Concepts sample questions. You can Evaluate your level of preparation in Basic Concepts by Taking the Q4Interivew Basic Concepts Online Mock Test based on most important questions. All the Basic Concepts practice questions given here along with answers and explanations are absolutely free, you can take any number of time any mock Test.

## Why C Programming Basic Concepts?

In this practice section, you can practice C Programming Questions based on "Basic Concepts" and improve your skills in order to face the interview, competitive examination, IT companies Written exam, and various other entrance tests (CAT, GATE, GRE, MAT, Bank Exam, Railway Exam etc.) with full confidence.

## Where can I get C Programming Basic Concepts questions and answers with explanation?

Q4Interview provides you lots of fully solved C Programming (Basic Concepts) questions and answers with Explanation. Solved examples with detailed answer description, explanation are given and it would be easy to understand. You can download C Programming Basic Concepts quiz questions with answers as PDF files and eBooks.

## Where can I get C Programming Basic Concepts Interview Questions and Answers (objective type, multiple-choice, quiz, solved examples)?

Here you can find objective type C Programming Basic Concepts questions and answers for interview and entrance examination. Multiple choice and true or false type questions are also provided.


text:
24/3x(5-9)

2. Originally Posted by breanna007
24/3x(5-9)
First in paranthesis,
$24/3 \times 4$
Now since you have multiple/divide go left to right,
$8\times 4$
$32$

3. Originally Posted by ThePerfectHacker
First in paranthesis,
$24/3 \times 4$
Now since you have multiple/divide go left to right,
$8\times 4$
$32$
Ahm. I think TPH meant -32.
5 - 9 is -4, not 4, hence you got the negative what he said you get.

4. Originally Posted by ThePerfectHacker
First in paranthesis,
$24/3 \times 4$
Now since you have multiple/divide go left to right,
$8\times 4$
$32$
Slight error:
$\frac{24}{3} \times (5 - 9) = 8 \times (-4) = -32$

-Dan


text:
# The end of this journey

A great wise man once said that
although it is only a foot or two away,
this journey can take you many years.
The end of this journey is what you seek, whether you know it or not.

hint:

No matter you are young or old, the mind can be cold.

To answer this question, there are two parts:

What is this destination? Where are you traveling from?

Note:

This is a true story.

• Who is this "great wise man" and when did this "true story" happened? – user9174 Feb 22 '15 at 6:07
• About the "true story" , it was said by Srinivas Arka, whom I know very well. He wrote a book called Adventures in Self Discovery. – Michael Rize Feb 24 '15 at 4:17

What is this destination?

Heart

Where are you traveling from?

Mind

A great wise man once said that although it is only a foot or two away,

this journey can take you many years.

We try to overcome illusions of our mind and find who we really are deeply in our heart.

The end of this journey is what you seek, whether you know it or not.

Your mind may not know what you seek, but it's your heart that feels seeking. So whether we know it or not, we seek to find who we are and what is that we really seek.

• Bravo +1 .. Congrats on receiving the bounty. Excellent answer. Also, congratulations on this being your first accepted answer on this site! – Michael Rize Feb 22 '15 at 2:19
• What is this destination? Heart , thats weard – Sven van den Boogaart Feb 22 '15 at 11:27
• @MichaelRize But he hasn't received the bounty yet! Also, nice riddle :-) – Rand al'Thor Feb 24 '15 at 11:21

What is this destination?

Where are you traveling from?

A great wise man once said that although it is only a foot or two away,

Most people will grow a foot, or two, from adolescence to adulthood

this journey can take you many years.

Yes, it will

The end of this journey is what you seek, whether you know it or not.

No child wants to stay a child forever

• I had not considered this solution, good job. However, not all of us are adolescent now, so it does not meet all criteria. The correct answer applies to all people, young or old. "The end of this journey is what you seek." – Michael Rize Feb 18 '15 at 0:19
• Fair enough, my take on it was that there was nothing to say people might have already taken the journey. So yes, not everyone is adolescent right now but they were and they took that journey. Back to the drawing board for me! – Mashton Feb 18 '15 at 9:54

The destination is:

Death

You are travelling to there from:

Life

Why?

although it is only a foot or two away,

You are buried at that depth

this journey can take you many years.

It takes pretty much your whole life

The end of this journey is what you seek, whether you know it or not.

We are all headed there, whether we realize it or not.

• I do believe people are buried deeper than that, otherwise nice try. Also, most people do not seek death. – Michael Rize Feb 17 '15 at 8:31
• This is exactly what I would have said! +1 – Rand al'Thor Feb 17 '15 at 11:04
• "6 feet under" is the correct measurement. – Michael Rize Feb 18 '15 at 0:25

I call upon the lessons my father has taught me when I answer this:

The first step. It has been said that the first step toward any goal is always the most difficult one, in that it means beginning your journey requires motivation that you may need to accumulate over the years. The distance in the idiom is measured as a foot or two because that's the accepted length of a human stride. Sometimes, the end of your journey is not what you expected when you started. It's difficult to spell out a specific to and from, but I suppose the best summary would be
To: The first step towards a goal
From: Figuratively standing in place, unmotivated

• I like this answer. However, "The end of this journey is what you seek". The first step is the journey, not the destination. – Michael Rize Feb 18 '15 at 0:31

What is this destination?

Marriage

Where are you traveling from?

Being single / alone

A great wise man once said that although it is only a foot or two away,

The person you feel an affection for can be right in front of you

this journey can take you many years.

Getting to know someone, figuring out compatibility, building a large degree of intimacy, and allowing for life plans can all make getting to marriage take a long time

The end of this journey is what you seek, whether you know it or not.

The end of the journey would be the wedding, finally reaching the goal you set out for. You may be seeking it as a way to "cement" your relationship in place

• Very clever, but again does not meet all criteria as not everyone is single. – Michael Rize Feb 18 '15 at 0:30

What is this destination?

Knowledge

Where are you traveling from?

Ignorance

...although it is only a foot or two away,

A comfortable distance for books (well, maybe now a tablet or Kindle)

...this journey can take you many years.

...The end of this journey is what you seek, whether you know it or not.

Wisdom / Enlightenment

What is this destination?

Truth.

Where are you traveling from?

Illusion.

## protected by Rand al'ThorFeb 24 '15 at 11:18

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).


text:
# Maths for Cryptography

Following are the basic mathematical elements required for an understanding of cryptography.

## Primes and Coprimes

### Basics

If you don't know what a prime is you probably shouldn't be doing this course.

$\pi\left(x\right)$ is the number of primes less than or equal to x.

For $x \geq 17$ this can be approximated by $${x \over ln x} < \pi\left(x\right) < 1.25506 \cdot {x \over ln x}$$

### Coprimes

Integers $a, b$ are coprime or relatively prime if they have no common factors (nothing divides them both).

This is usually tested for using the Greatest Common Denominator algorithm (or gcd), where $coprime(a, b) \iff gcd(a, b) = 1$

#### Euler totient

$\phi\left(n\right)$ denotes how many natural numbers (positive integers) that are less than $n$ are coprime with $n$

$\phi\left(n\right)$ is known as the Euler Totient function

If we know the prime factors of $n$ then $\phi\left(n\right)$ can be calculated as $$\phi\left(n\right) = n\prod_{p} \left(1-{1\over p}\right)$$

where $p$ is a distinct prime factor of $n$

### Smoothness

An integer $n$ is said to be $B-smooth$ for some $B$ (e.g. 50-smooth) if all of its prime factors are less than or equal to $B$

Note this generally means that $B$ is the lowest such number for $n$, meaning it is $n$'s largest prime factor but this is not always the case.

If $B$ is much smaller than $n$ then we tend to say "$n$ is smooth".

#### Importance

There exist quick algorithms for factoring smooth numbers, even when they are large, so one must avoid using smooth numbers in techniques that rely upon prime factorisation for security.

## Modulo Arithmetic

The set $Z_n = \left\{0, ..., n-1\right\}$ contains the integers that can exist in a $mod\ n$ equation.

For example $Z_5 = \left\{0, 1, 2, 3, 4\right\}$

Each of the numbers $x$ in $Z_n$ can also be considered an equivalence class of all numbers that are congruent to $x$ ($mod\ n$).

### Multiplicative inverse

If $a$ is in $Z_n$ then the multiplicative inverse of $a\ mod\ n$ is a unique $x\in Z_n$ such that $ax \equiv 1\ (mod\ n)$

$x$ only exists if $a$ and $n$ are coprime ($gcd\left(a, b\right) = 1$)

$Z^*_n$ consists of all numbers in $Z_n$ that are coprime with $n$.

It is important to note here that this includes $1$.

$Z^*_n$ is closed under multiplication and, as should be obvious, contains $\phi\left(n\right)$ elements.

If $n$ is prime then $Z^*_n = Z_n\backslash0$

(so $Z^*_n$ contains all non-zero elements of $Z_n$)

### Fermat's Little Theorem

This can be stated in two ways:

• If $p$ is prime then $a^p \equiv a (mod\ n)$
• If $p$ is prime and $p$ is coprime with $a$ then $a^{p-1} \equiv 1 (mod\ n)$

This theorem can be used as a simple probabilistic primality test amongst other uses.

### Euler's Theorem

If $a$ and $n$ are coprime then $$a^{\phi\left(n\right)} \equiv 1\ (mod\ n)$$

This theorem can be used to reduce large powers when working $mod\ n$ $$5^{79}\ mod\ 6 = (5^2 \times 5^2)^{19} \times 5^3$$

as $5^2 = 25 \equiv 1\ mod\ 6$, this is $$\left(1 \times 1\right)^{19} \times 5^3 = 125 \equiv 5\ (mod\ 6)$$

In general if $x \equiv y\ (mod\ n)$ then $a^x \equiv a^y\ (mod\ n)$ or if $x$ and $y$ are equivalent $mod\ n$ then so is a number to the power of each.

### Cyclic Groups

#### Order

For $a \in Z^*_n$ ($a$ is coprime with $n$ and $a < n$) the order of $a$ is that if you start with $t = 1$ and increment $t$ repeatedly, then the order of $a$ is the first value for $t$ for which $a^t \equiv 1\ (mod\ n)$

If this $a \geq 2$ and its order ($t$) is $\phi\left(n\right)$ then $Z^*_n$ is cyclic. This means that when you were raising $a$ to the incrementing $t$ you will have touched every element in $Z^*_n$ before reaching $t$.

Or equivalently every element in $Z^*_n$ is reachable from every other such element by simple exponentiation.

Such an $a$ is called a generator for $Z^*_n$ because one can create all of $Z^*_n$ from it. Note that not all $b \in$Z^*_b$will be generators. It turns out $Z^*_n$is cyclic iff $n$is either $2$, $4$, a power of an odd prime, or twice a power of an odd prime. #### Discrete Logarithms The discrete logarithm of $b$with respect to $g$(for some generator $g$) is the $x$such that $g^x \equiv b\ (mod\ n)$. There is an efficient algorithm for computing discrete logarithms in $Z^*_p$if $p-1$is smooth. I'm not entirely sure on this because the slides are ambiguous. They say "if $p-1$has smooth factors" but factors are primes and primes aren't smooth? I'm also assuming $p$is prime, otherwise it would be $n\$.

Back to Computer Security