text:
# Elementary counting: multiplication?

It is certainly a silly question.

When we store $n$ students in $N$ different day, we say the following for the first student there is $N$ different choices, for the second $N-1$, etc. So that there is $$N\cdot (N-1)\cdots(N-n+1)$$ possibilities.

But I never really understanding why we do a multiplication.

For exemple let's say we have $2$ students Bob and Lea and $3$ days. For Bob there is $3$ choices so that for Lea there is $2$ choices. And then $3+2=5$ choices and the "correct" answer is $3\times 2=6.$

I cannot think where I am wrong.

• The choices are independent of each other. Independence means multiplication. Jun 7, 2017 at 9:43

$$B1\text{ or }B2\text{ or }B3\text{ or }L1\text{ or }L2.$$
$$B1L2\text{ or }B1L3\text{ or }B2L1\text{ or }B2L3\text{ or }B3L1\text{ or }B3L2.$$
$$\begin{matrix}&B1&B2&B3\\L1&&\circ&\circ\\L2&\circ&&\circ\\L3&\circ&\circ&\end{matrix}$$ where there are three rows and two dots per row.


text:
# Vector spaces

1. Aug 30, 2004

### Oxymoron

I am in need of some guidance on a question concerning vector spaces and spanning sets.

Q) Suppose that V is a vector space over F and {v1,...,vn} ⊂ V.
a) Prove that if {v1,...,vn} spans V, then so does {v1-v2,v2-v3,...,v(n-1)-v(n),vn}.

2. Aug 30, 2004

### Tom Mattson

Staff Emeritus
Please post what you've got so far.

3. Aug 31, 2004

### Oxymoron

What we have here is a vector space V (of unknown dimension, other than it is more than n) and a set S of n vectors (ie. dimS = n). We are given that S ⊂ V, ie. S is a subset of V. We want to prove that if S (of n vectors) spans V then so does T (also of n vectors) spans V. Where T = {v1-v2,v2-v3,...,v(n-1) - vn,vn} This is a good start because the number of vectors in S is the same as the number of vectors in T.

The question asks us to prove {v1-v2,v2-v3,...,v(n-1) - vn,vn} spans V IF S spans V. So we can assume S spans V without having to be concerned that it doesn't. Assuming S spans V opens up a lot of useful theorems that we can use to our advantage. Since S spans V then that means that every vector v in V must be able to be written as a linear combination of vectors in S.

PROOF:
Take any v ∈ V. Then since S spans V, v can be written as

v = c1v1 + c2v2 + ... + cnvn

Im not sure how to continue past this. I have a lot of fragmented ideas.

Last edited: Aug 31, 2004
4. Aug 31, 2004

### matt grime

S is just a set so dimS makes no sense.

If dimV is (strictly) greater than n, then S can't possibly span.

Can I guess that those are slips of the fingers, and answer what I think the question might be?

T spans the same subvector space as S since every vector in T is a combination of vectors in S and vice versa, do you see that?

5. Aug 31, 2004

### shmoe

You want to eventually get v as a linear combination of the vectors in T, in other words you want to find coefficients $$d_1,\ldots,d_n$$ where:

$$v=d_1(v_1-v_2)+d_2(v_2-v_3)+...+d_{n-1}(v_{n-1}-v_n)+d_nv_n$$

Can you find some $$d_i$$'s that satisfy this equation in terms of the $$c_i$$'s, which you already know exist?

matt's method is simpler than directly applying the definition of span like this. You should be able to understand both ideas!

6. Aug 31, 2004

### matt grime

i'd have just said that my idea was your idea without some of the messy bits left out (ie don't actually find the d's and c's since existence is all we require)

7. Aug 31, 2004

### shmoe

I agree your way is simpler, but it's always usefull to have a slightly different way of tackling a problem. Whether the difference is large enough to call them different ideas is debatable, but I'd say it's significant enough to try to understand both approaches, especially for someone first learning linear algebra.

Knowing how to work out the d's from the c's will let you write the vectors of V in terms of the vectors in T. This of course isn't needed to solve this particular problem but can be a handy thing to have some practice doing. It also gives a more "hands on" feel to how linear combinations of S and T are related to one another.

8. Aug 31, 2004

### Oxymoron

Thanks for the help guys. First question though: how do you LaTEX to display in your posts?

Matt, I see how every vector in T is a linear combination of vectors in S. Since S spansV and S is a subset of V then S contains a basis for V right?
Then since T is a linear combination of vectors in S, T also contains a basis for V. If T contains a basis of V, and since T ⊆ S ⊂ V then T must span V.

Take any v ∈ V.

v=c1v1 + c2v2 + ... + cnvn

then there exist di ∈ F such that

v=d1(v1-v2) + d2(v1-v2) + ... + d(n-1)(v(n-1)-vn + dnvn

Therefore T is a linear combination of vectors in S (are you sure that you can just assume existence?).

9. Aug 31, 2004

### shmoe

Click on the Latex in a post and it will display the code used. You can also check out https://www.physicsforums.com/misc/howtolatex.pdf

Correct, but a basis is not needed for this problem. Since you know the vectors in T are linear combinations of the vectors in S, what can you say about the sets T and span S? What does this then tell you about the sets span T and span S?

This reasoning is incorrect. The set {v1-v1,v2-v2} is also composed of linear combinations of the vectors in S, but it's not going to contain a basis for V.

The part in bold could be left out and this is true by what it means for T to contain a basis of V. However, we don't know this is true yet.

I'm not sure what you are trying to say here, T isn't a linear combination of anything, it is a set. You can't just assume existance of the d's. But you can use the fact that those c's exist to find d's that work and make this second equation true.

10. Sep 1, 2004

### matt grime

Here's how I think of this.

Let S be a spanning set of vectors for a vector space V.

Let T be another set of vectors such that every element in S is a linear combination of elements in T (as is clearly the case here)

Given any vector v in V, it can be written as a combination of elements in S. As every element in S can be written in terms of elements in T, T must span too.

For example, suppose the elements in S are s_1, s_2, ... s_n, and the elements in T are t_1,t_2 ,...., t_r note n and r are not necessarily the same.

suppose that s_1 = t_1+3t_3, for example

if S spans and v = as_1+bs_2+cs_3+...

then we can substitute for s_1 in terms of the elements in T, and repeat for all other s_i using the relations there.

Note which sets are which S spans V and every element in S is a combination of elements in T, hence T spans V too.

There is absolutely no need to invoke a the word basis at all in this question.

Last edited: Sep 1, 2004
11. Sep 1, 2004

### Oxymoron

Should this read "Let T be another set of vectors such that every element in T is a linear combination of elements in S"?

How exactly is T a set of vectors that are linear combinations of the vectors in S? I know this is a dumb question. I just don't see it

This is not enough to convince me. How do you know that $$v$$ can be written as a linear combination of elements in $$S$$ and how do you know that every element in $$S$$ can be written in terms of elements in $$T$$.

I am really NOT getting this!! So I will write exactly what I have... I need to be able to write down a solid proof. I can't just say that take any v in V, then it can be written as a linear combination of etc.... I know to start the proof I have to take any v in V.

Take any $$\textbf{v} \in V$$.

Then this vector can be written as a linear combination of vectors in $$S$$ because $$S$$ spans $$V$$.

$$\textbf{v} = c_1 v_1 + c_2 v_2 + \dots + c_n v_n$$

Now I need to show that every vector in $$T$$ can be written as a linear combinations of vectors in $$S$$ such that $$T = \{ v_1 - v_2, \dots , v_{n-1} - v_n, v_n \}.$$ How would I show this?

Once I show that every vector in $$T$$ can be written as a linear combinations of vectors in $$S$$ then my chosen $$\textbf{v}$$ can also be written as a linear combination of vectors in $$T$$ such that

$$\textbf{v} = d_1(v_1 - v_2) + d_2(v_2 - v_3) + \dots + d_n(v_n)$$

Therefore $$T$$ spans $$V$$ if I can find $$d_i$$'s which satisfy the above equation.

I hope you guys understand that I appreciate your time spent on my issue. Hopefully some day I will understand this question! - I have still yet to prove that if S is a linearly independent subset of V then so is T. But one question at a time...

12. Sep 3, 2004

### shmoe

This was your assumption that S is a spanning set of V.

You can sit down and do it. The left side of the equations below will be the vectors in S, the right side will be linear combinations of the vectors in T:

$$v_n=v_n$$
$$v_{n-1}=(v_{n-1}-v_{n})+v_n$$
$$v_{n-2}=(v_{n-2}-v_{n-1})+(v_{n-1}-v_{n})+v_n$$

and so on (do you know how to get these linear combinations?). This will prove that the vectors in S are in span T. Once you know this, you are pretty much finished. Since S is a set of vectors contained in span T, and span T is a vector space, the span S is containted in span T (a linear combination of vectors in a vector space is in that vector space again). Can you fill in the last few details that finish it off?

We can carry on in a different direction though, one that's appealing directly to the definition of span:

Fine so far.

There's more than one way. Since we have the vectors of S as linear combinations of vectors in T (see above), you can just substitute them into your $$\textbf{v} = c_1 v_1 + c_2 v_2 + \dots + c_n v_n$$ equation, and group the T vectors. Try doing this and report back on what you get.

This is fine. You should be able to actually write down the d's from the c's.

It will come. This can be difficult the first time you see it, but it gets much easier with practice.

13. Sep 3, 2004

### matt grime

no i meant exactly what i said. consider the counter example where T is a subset of S with a strictly smaller span. T then doesn't span the same vector space S spans which is what I showed.

Every vector in S is a linear combination of vectors in T, as shmoe showed, therefore

span(S) < span(T)

here < means containment of vector spaces

every vector in T is also a combination of vectors in S

thus span(T) < span(S)

hence the spans are equal.

Last edited: Sep 3, 2004
14. Sep 17, 2004

### mathwonk

this is basically the same question: start from the square identity matrix and introduce a "minus one" just above all the diagonal entries except the first one. Then ask if you can return this matrix to the identity matrix by elementary row operations.

then exactly the same operations suffice to express your first set of vectors in terms of your second set.

15. Sep 17, 2004

### HallsofIvy

Staff Emeritus

You might want to start by writing out the definition of "span" .

16. Sep 17, 2004

### mathwonk

or do my exercise with row operations and then you will have essentially been doing the operations in the definition of the word "span" (i.e. linear combinations).

format: plain


text:
Article | Open | Published:

# A Bayesian mixture model for clustering droplet-based single-cell transcriptomic data from population studies

## Abstract

The recently developed droplet-based single-cell transcriptome sequencing (scRNA-seq) technology makes it feasible to perform a population-scale scRNA-seq study, in which the transcriptome is measured for tens of thousands of single cells from multiple individuals. Despite the advances of many clustering methods, there are few tailored methods for population-scale scRNA-seq studies. Here, we develop a Bayesian mixture model for single-cell sequencing (BAMM-SC) method to cluster scRNA-seq data from multiple individuals simultaneously. BAMM-SC takes raw count data as input and accounts for data heterogeneity and batch effect among multiple individuals in a unified Bayesian hierarchical model framework. Results from extensive simulation studies and applications of BAMM-SC to in-house experimental scRNA-seq datasets using blood, lung and skin cells from humans or mice demonstrate that BAMM-SC outperformed existing clustering methods with considerable improved clustering accuracy, particularly in the presence of heterogeneity among individuals.

## Introduction

Single-cell RNA sequencing (scRNA-seq) technologies have been widely used to measure gene expression for each individual cell, facilitating a deeper understanding of cell heterogeneity and better characterization of rare cell types1,2. Compared to early generation scRNA-seq technologies, the recently developed droplet-based technology, largely represented by the 10x Genomics Chromium system, has quickly gained popularity because of its high throughput (tens of thousands of single cells per run), high efficiency (a couple of days), and relatively lower cost (<\$1 per cell)3,4,5,6. It is now feasible to conduct population-scale single-cell transcriptomic profiling studies, where several to tens or even hundreds of individuals are sequenced7.

A major task of analyzing droplet-based scRNA-seq data is to identify clusters of single cells with similar transcriptomic profiles. To achieve this goal, classic unsupervised clustering methods such as K-means clustering, hierarchical clustering, and density-based clustering approaches8 can be applied after some normalization steps. Recently, scRNA-seq tailored unsupervised methods, such as SIMLR9, CellTree10, SC311, TSCAN12, and DIMM-SC13, have been designed and proposed for clustering scRNA-seq data. Supervised methods, such as MetaNeighbor, have been proposed to assess how well cell-type-specific transcriptional profiles replicate across different datasets14. However, none of these methods explicitly considers the heterogeneity among multiple individuals from population studies. In a typical analysis of population-scale scRNA-seq data, reads from each individual are processed separately and then merged together for the downstream analysis. For example, in the 10x Genomics Cell Ranger pipeline, to aggregate multiple libraries, reads from different libraries are downsampled such that all libraries have the same sequencing depth, leading to substantial information loss for individuals with higher sequencing depth. Alternatively, reads can be naively merged across all individuals without any library adjustment, leading to batch effects and unreliable clustering results.

Similar to the analysis of other omics data, several computational approaches have been proposed to correct batch effects for scRNA-seq data. For example, Spitzer et al.15 adapted the concept of force-directed graph to visualize complex cellular samples via Scaffold (single-cell analysis by fixed force- and landmark-directed) maps, which can overlay data from multiple samples onto a reference sample(s). Recently, two new methods: mutual nearest neighbors16 (MNN) (implemented in scran) and canonical correlation analysis (CCA)17 (implemented in Seurat) were published for batch correction of scRNA-seq data. All these methods require the raw counts to be transformed to continuous values under different assumptions, which may alter the data structure in some cell types and lead to difficulty of biological interpretation.

We first conducted an exploratory data analysis to demonstrate the existence of batch effect in multiple individuals using both publicly available and three in-house synthetic droplet-based scRNA-seq datasets, including human peripheral blood mononuclear cells (PBMC), mouse lung and human skin tissues. Detailed sample information was summarized in Fig. 1a and Supplementary Table 1. We use human PBMC as an example. We isolated from whole blood obtained from 4 healthy donors and used the 10x Chromium system to generate scRNA-seq data. We also included one additional healthy donor from a published PBMC scRNA-seq data4 to mimic the scenario where we combine the local dataset with the public datasets. In this cohort, sample 1 and sample 2 were sequenced in one batch; sample 3 and sample 4 were sequenced in another batch; sample 5 was downloaded from the original study conducted by 10x Genomics4. As an exploratory analysis, we produced a t-SNE plot based on the first 50 principal components (Supplementary Fig. 1) of all cells from these 5 donors and observed a clear batch effect: samples from the same batch tend to cluster together.

This illustrative example demonstrates the importance and urgent need for well characterizing different sources of variability and correcting potential batch effects among droplet-based scRNA-seq datasets collected from multiple individuals. In addition, due to the computational burden, many methods cannot be scaled up to analyze population-scale droplet-based scRNA-seq data with tens of thousands of cells collected from many individuals under various conditions. In this study, we propose a BAyesian Mixture Model for Single Cell sequencing (BAMM-SC) to simultaneously cluster large-scale droplet-based scRNA-seq data from multiple individuals. BAMM-SC directly works on the raw counts without any data transformation and models the heterogeneity from multiple sources by learning the distributions of signature genes in a Bayesian hierarchical model framework. In the following sections, we will describe our method, benchmark its performance against existing clustering methods in simulation studies, and evaluate our method for its accuracy, stability, and efficiency in three in-house synthetic scRNA-seq datasets including PBMCs, skin, and lung tissues from humans or mice.

## Results

### Overview of BAMM-SC

BAMM-SC represents a Bayesian hierarchical Dirichlet multinomial mixture model, which explicitly characterizes three sources of heterogeneity (i.e., genes, cell types, and individuals) (see Methods). Figure 1b provides an overview of the model structure in BAMM-SC, which directly models cell-type specific genes’ unique molecular identifier (UMI) counts and their heterogeneity among different individuals through a hierarchical distribution structure in a Bayesian framework. Our method has the following three key realistic assumptions. First, cell type clusters are discrete, and each cell belongs to one specific type exclusively. Second, heterogeneity exists among different individuals and across different cell types. The heterogeneity of the same cell type among different individuals is smaller than the heterogeneity across different cell types within the same individual. Third, cells of the same cell type share a similar gene expression pattern. That is, the underlying statistical distributions for cells within the same cell type are assumed to be the same. The mathematical model representations are included and explained in Supplementary Methods. Compared to other clustering methods which ignore individual level variability, BAMM-SC has the following four key advantages: (1) BAMM-SC accounts for data heterogeneity among multiple individuals, such as unbalanced sequencing depths and technical biases in library preparation, and thus reduces the false positives of detecting individual-specific cell types. (2) BAMM-SC borrows information across different individuals, leading to improved power for detecting individual-shared cell types and higher reproducibility as well as stability of the clustering results. (3) BAMM-SC performs one-step clustering on raw UMI count matrix without any prior batch-correction step, which is required for most clustering methods in the presence of batch effect. (4) BAMM-SC provides a statistical framework to quantify the clustering uncertainty for each cell in the form of posterior probability for each cell type (see Methods).

### Simulation studies

We have conducted comprehensive simulation studies to benchmark the performance of BAMM-SC. Specifically, we simulated droplet-based scRNA-seq data collected from multiple individuals from the posited Bayesian hierarchical Dirichlet multinomial mixture model (see Methods and Supplementary Methods). We considered different experimental designs, including different heterogeneities among multiple individuals and different numbers of individuals (Fig. 2). In our posited hierarchical model, the log normal prior distribution LN $$(\mu _{ik},\sigma _{ik}^2)$$ measures the heterogeneity of gene i in cell type k among multiple individuals, where $$\mu _{ik}$$ and $$\sigma _{ik}^2$$ are related to the mean and variation of gene expression. Without loss of generality, we used the mean of $$\sigma _{ik}^2$$ across all genes and all cell types to quantify the overall individual level heterogeneity. We applied BAMM-SC to each synthetic dataset, and compared the inferred cell type label of each single cell with the ground truth, measured by adjusted Rand index (ARI)18. We compared BAMM-SC with other competing clustering methods (K-means, TSCAN, SC3, and Seurat), which are either methods from different clustering categories or recommended by recent reviews on clustering methods for single-cell data19,20. Since none of methods model batch effects and therefore each needs to be combined with a batch correction method as a preprocessing step in data analysis. We applied two recently published and prevalent methods srcan MNN16 and Seurat CCA17 prior to these clustering methods so that each combination can be a fair comparison with BAMM-SC, which does not need a separate batch correction step.

Specifically, we compared BAMM-SC with the other nine competing methods (MNN+K-means, MNN+TSCAN, MNN+SC3, MNN+Seurat, CCA+K-means, CCA+TSCAN, CCA+SC3, CCA+Seurat, and DIMM-SC) in the simulation studies. Noticeably, DIMM-SC, our previously developed method for clustering scRNA-seq data from a single individual, also takes the raw UMI count matrix as the input without any batch effect correction or data transformation. We pooled single cells from different individuals together while ignoring each individual label, and then applied DIMM-SC to the pooled data. We simulated 100 datasets and summarized the corresponding ARIs for each method.

As shown in Fig. 2a, BAMM-SC consistently outperformed the other nine competing methods across a variety of individual level heterogeneities by achieving higher average ARI and lower variation of ARI among 100 simulations. As expected, the performance of all ten clustering approaches decreases as the among individual heterogeneity increases, measured by the mean $$\sigma _{ik}^2$$ values. In Fig. 2b, with the increase of number of individuals, BAMM-SC achieved higher ARI, while ARIs of other methods either remained stable or decreased.

Furthermore, we performed comprehensive simulation studies by generating simulated scRNA-seq datasets from different number of cell type clusters (Supplementary Fig. 2a), different overall sequencing depths (Supplementary Fig. 2b), and different cell-type-specific heterogeneities (i.e., the mean difference of gene expression profiles between two distinct cell types) (Supplementary Fig. 2c). BAMM-SC consistently outperformed other methods in terms of accuracy and robustness in all these scenarios. Taken together, our comprehensive simulation studies have demonstrated that, when data are generated from the true model, BAMM-SC is able to appropriately borrow information across multiple individuals, account for unbalanced sequencing depths, and provide more accurate and robust clustering results than other competing methods.

To evaluate the robustness of BAMM-SC when data generation model is mis-specified, we simulated additional datasets using R package Splatter21, a commonly used tool for scRNA-seq data simulation using a completely different model. To make our simulated data a good approximation to the real data, we first downloaded the raw UMI count matrix of a purified B-cell scRNA-seq dataset from the 10x Genomics website (https://support.10xgenomics.com/single-cell-gene-expression/datasets/1.1.0/b_cells), and used the function splatEstimate to estimate the parameters related to mean of gene, library size, expression outlier, dispersion across genes, and dropout rate. We assumed cell types are shared across multiple individuals, where each individual is treated as one batch with the same number of cells and genes. We further specified batch parameters and differential expression parameters to generate scenarios with different amount of group effect (i.e., cell type differences) and batch effect. As shown in Fig. 3, BAMM-SC still outperformed most other competing methods in terms of clustering accuracy in all scenarios, although the improvement is less substantial than our own model simulations, which is expected.

### Real data analysis on human PMBC dataset

For aforementioned human PBMC samples, we first pooled cells from five donors together, filtered lowly expressed genes that were expressed in less than 1% cells. We then extracted the top 1000 highly variable genes based on their standard deviations. As shown in Supplementary Fig. 3, we identified seven types of PBMCs based on the biological knowledge of cell-type-specific gene markers (Supplementary Table 2). Using these gene markers, >70% single cells can be assigned to a specific cell type. Since there is no gold standard for clustering analysis in this real dataset, we used the labels of these cells as the approximated ground truth to benchmark the clustering performance for different clustering methods. Cells with uncertain cell types were removed when calculating ARIs.

Similar to the simulation studies, we applied ten clustering methods on these samples and repeated each method ten times to evaluate the stability of its performance (Table 1). The total number of clusters was set as seven based on the biological knowledge from cell-type-specific gene markers. As shown in Table 1, BAMM-SC achieved the highest ARI for human PBMC samples compared to all other competing methods. Both TSCAN and Seurat are deterministic clustering methods and therefore they generate identical results for ten analyses.

We further generated t-SNE plots with each cell colored by their cell-type classification based on specific gene markers (i.e., the approximated truth) (Fig. 4a (left figure)) and cluster labels inferred by BAMM-SC (Fig. 4a (middle figure)), respectively. Despite some dendritic cells were wrongly identified as CD16+Monocytes, these two plots are similar to each other (ARI = 0.532), suggesting that BAMM-SC performed well in human PBMC samples compared with other clustering methods.

Moreover, we calculated the averaged cell proportions of each cell type inferred from BAMM-SC among ten runs for five PBMC samples, compared with cell proportions calculated from the approximated truth based on gene markers. Figure 4a (right figure) shows that the proportions inferred from BAMM-SC are close to the truth, suggesting that BAMM-SC can adequately account for batch effect when clustering cells from multiple individuals. We also generated t-SNE projection plots colored by cluster labels inferred by other methods: MNN+K-means clustering (Supplementary Fig. 4a), MNN+TSCAN (Supplementary Fig. 4b), MNN+SC3 (Supplementary Fig. 4c), MNN+Seurat (Supplementary Fig. 4d), CCA+K-means (Supplementary Fig. 4e), CCA+TSCAN (Supplementary Fig. 4f), CCA+SC3 (Supplementary Fig. 4g), CCA+Seurat (Supplementary Fig. 4h), and DIMM-SC (Supplementary Fig. 4i).

### Real data analysis on mouse lung dataset

We collected lung mononuclear cells from four mouse samples under two conditions: Streptococcus pneumonia (SP) infected (sample 1 and 2) and naive (sample 3 and 4). Supplementary Figure 5 shows the t-SNE plot of lung mononuclear cells from four mouse samples. Similar to the analysis of PBMC samples, after filtering lowly expressed genes, we pooled cells from 4 mice together and extracted the top 1000 highly variable genes. As shown in Supplementary Fig. 6, we identified six types of cells based on the biological knowledge of cell-type specific gene markers (Supplementary Table 3). Taken together, >66% of single cells can be assigned to a specific cell type. Therefore, we used the labels of these cells as the approximated truth and removed cells with uncertain cell types from the downstream analysis.

Figure 4b (left figure) and Fig. 4b (middle figure) show the t-SNE plots with each cell colored by their cluster label based on cell-type-specific gene markers and cluster labels inferred by BAMM-SC, respectively. These two are highly similar (ARI = 0.910), indicating the outstanding performance of BAMM-SC. Table 1 shows that BAMM-SC considerably outperformed other nine clustering methods in terms of ARI. We also generated t-SNE plots colored by cluster labels inferred by other competing clustering methods (Supplementary Fig. 7). As shown in Supplementary Fig. 8, the proportions of neutrophils in SP infected samples (sample 1 and sample 2) are much higher than the proportions in naïve samples (sample 3 and sample 4). This is consistent with the fact that infections by bacteria and viruses may increase the number of neutrophils, which is a necessary reaction by the body22,23. Interestingly, the proportion of cell types in naïve sample 3 is different from others, which may due to unsatisfactory sample quality or unexpected bacterial infections.

### Real data analysis on human skin dataset

To evaluate the clustering performance of BAMM-SC in solid human tissues, we collected skin samples from five healthy donors that are part of a systemic sclerosis study24. Figure 1a and Supplementary Table 1 list the detailed sample information and Supplementary Fig. 9 shows the t-SNE plot of cells from five human skin samples after the data processing similar to previous analyses. As shown in Supplementary Fig. 10, we identified eight major types of cells based on the biological knowledge of cell-type-specific gene markers (Supplementary Table 4). Taken together, >67% of single cells can be assigned to a specific cell type. Similar to the other two real data analyses, we used the labels of these cells as the approximated truth and removed cells with uncertain cell types from the downstream analysis.

As shown in Fig. 3c, BAMM-SC performed well in human skin samples, since the t-SNE plot with each cell colored by their cell-type label based on gene markers is highly similar to the plot generated from the clustering result of BAMM-SC (ARI = 0.843). Also, BAMM-SC achieved higher ARI compared with all the other clustering methods (Table 1). As comparisons, we generated t-SNE plots colored by cluster labels inferred by different clustering (Supplementary Fig. 11).

### Other evaluation criteria

To further demonstrate the validity of BAMM-SC, we calculated the confusion matrix for three real datasets and reported the clustering accuracy (defined as the proportion of cells being classified into the correct cell-type cluster) (Supplementary Table 5, Supplementary Methods). Our method outperformed other competing methods in all three datasets. In addition, we performed a flow cytometry experiment, a gold standard method for quantifying cell population through cell surface markers, on the sample 3 from the human PBMC dataset, which has an additional aliquot from the same pool of cells. We used FlowJo software to gate each cell population through specific antibodies and calculated the percentage of each cell type. Then, we compared the proportions of different cell types from flow cytometry and the clustering result of BAMM-SC from scRNA-seq. Supplementary Figure 12 shows that the proportion of cells in each cell type classified by BAMM-SC is consistent with that being estimated by flow cytometry. We also calculated the Pearson’s correlation coefficient of cell proportions for each clustering method (Supplementary Table 6). Despite the different technology, the high correlation (Pearson correlation coefficient is 0.98) suggests that BAMM-SC is able to adequately account for heterogeneity among multiple individuals and provide reliable clustering results. To be noted, unlike other clustering methods we considered, Seurat cannot directly pre-specify the number of clusters K. Rather it needs to set a resolution parameter that indirectly controls the cluster number. In all three real data sets, after an extensive grid search, we found the resolution parameter that yields the same number of clusters as the one based on the biological knowledge. Therefore, for the two Seurat clustering methods, instead of using the clustering assignments that produced the highest ARI among ten times analysis, we computed the confusion matrix and the proportions of different cell types based on this specific resolution parameter.

It is challenging to evaluate clustering algorithms in experimental data since the ground truth of cell type label is generally unknown. Other than using ARI based on cell-type-specific gene markers as approximated ground truth, we also used cluster stability and tightness to evaluate the clustering performance. Specifically, we calculated the average proportion of nonoverlap (APN)25 clustered cells and silhouette width26 in three real datasets, respectively. APN is a cluster stability measurement which evaluates the stability of a clustering result by comparing it with the clusters obtained by removing one feature (i.e., one gene in our study) at a time. It measures the average proportion of observations not placed in the same cluster under both cases. To make computation affordable in our real data analysis, after extracting the top 1000 highly variable genes, we compared the clustering results based on the full data (1000 genes) to the clustering results based on a subset of data with 100 genes randomly removed. We repeated this step ten times to calculate the APN. For cluster tightness, the silhouette width ranges from −1 to 1, where a higher value indicates that the observation is better matched to its own cluster and worse matched to other clusters. For both measurements, BAMM-SC achieved high cluster stability and high cluster tightness in most scenarios, compared with all other competing methods (Supplementary Table 7, Supplementary Table 8).

### Uncertainty assessment

Different from other deterministic methods, BAMM-SC has the ability to assess clustering uncertainty through the posterior probability for each cell to belong to each cell-type cluster. As shown in Supplementary Fig. 13, we highlighted vague cells in the t-SNE projection plot, where vague cells are defined as cells with the largest posterior cluster-specific probability <0.95. In the human PBMC samples, most of the vague cells (colored in red) are located at the boundary of different clusters, which reassuring the validity of the clustering results. In real data analysis, users can decide to remove vague cells under a user-specified criterion (based on the posterior probability) for the downstream analysis such as differential gene expression analysis within each cell type.

## Discussion

In summary, we have developed a novel Bayesian framework for clustering population-scale scRNA-seq data. BAMM-SC retains the raw data information by directly modeling UMI counts without data transformation or normalization, facilitating straightforward biological interpretation. The Bayesian hierarchical model enables the joint characterization of multiple sources of uncertainty, including single-cell level heterogeneity and individual level heterogeneity. Furthermore, BAMM-SC can borrow information across different individuals through its mixture hierarchical model structure and Bayesian computational techniques, leading to improved clustering accuracy. BAMM-SC is based on probabilistic models, thus providing the quantification of clustering uncertainty for each single cell.

Our model coupled with a computationally efficient MCMC algorithm is able to cluster large-scale droplet-based scRNA-seq data with feasible computational cost. For example, using 1000 highly variable genes, it takes about 1.5, 2.5, and 4.5 h when analyzing the 3 real datasets (human PBMC, mouse lung and human skin), respectively. For the simulated dataset consist of 10 individuals with 4000 cells each, the computational time for clustering is about 30 min. Supplementary Figure 14 demonstrates that the computational time of BAMM-SC increases approximately linearly with the increase of the number of cells in each individual, the number of individuals and the number of clusters, respectively. To further improve the computational efficiency, we provided a supervised clustering option in BAMM-SC for very large-scale datasets. Specifically, users can first apply BAMM-SC on a small subset of single cells in each individual, and save predicted cluster labels as well as other informative parameters such as $${\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}$$. Then for the remaining single cells, users can perform supervised classification via BAMM-SC instead of unsupervised clustering (see Methods). By clustering a small number of single cells, this procedure will substantially reduce the computational cost. We used the simulated dataset of ten individuals to demonstrate the effectiveness of this supervised option in Fig. 5. We simulated two datasets (Supplementary Methods): one dataset consists of 10 individuals with 400 cells each and the other dataset consists of 10 individuals with 4000 cells each. We selected a subset of cells in each individual as the training set and treated the remaining cells as the test set. We set the proportion of cells in the training set from 10 to 100% and reported the ARIs for both training and test sets. When the proportion equals 100%, there is no test data set, thus only ARI for the training set is reported. We repeated this simulation procedure 100 times and reported ARIs in Fig. 5 below. When the total number of cells in the training set is large enough (4000 in total or more), the prediction performance (measured by ARI) in the test set is saturated. For the dataset consists of 10 individuals with 4000 cells each, when we used 10% cells for training, it only takes ~90 s to obtain the clustering labels for all cells in both training and test sets with the similar performance from the full dataset. Therefore, for large datasets (e.g., >100 K cells), users can apply BAMM-SC to a smaller subset of cells in each individual to cluster distinct cell types, and then classify the remaining cells according to the predicted cell types. BAMM-SC is currently implemented in R/Rcpp with satisfactory computing efficiency to accommodate population scale scRNA-seq data. Further speed-up can be made through parallel computing or graphics processing unit.

In addition, we can predefine the number of clusters based on prior knowledge on the tissue or determine it using some standard model checking criterion such as Akaike's Information Criteria (AIC) or Bayesian Information Criteria (BIC). As shown in Supplementary Fig. 15, AIC and BIC work as expected in the analysis of simulated datasets and provide a reliable range of cluster numbers to guide real data analysis based on prior knowledge. However, in a biological study, the number of clusters is often considered as a continuum because of the nature of cell growth, so we recommend trying a range of cluster numbers in practice. BAMM-SC is shown to be robust against model mis-specification. In our simulation studies, we applied Splatter to simulate scRNA-seq data in which the data generation mechanism is different from our proposed BAMM-SC model. BAMM-SC still achieved higher clustering accuracy than other competing methods. In addition, we compared BAMM-SC with other clustering methods when the number of clusters is different from the true number of cell types. Supplementary Fig. 16 shows that BAMM-SC still achieved the highest ARI in most scenarios.

Other than MNN and CCA, several other approaches have been proposed to correct batch effect across multiple individuals. One straightforward approach is taking one individual as the reference, producing a low-dimensional embedding of it and then projecting the other individuals onto that embedding. To perform low-dimensional embedding, diffusion map27 is a tool for nonlinear dimension reduction and has recently been adapted for the visualization of single-cell gene-expression data. In addition, single-cell variational inference (scVI) is a scalable framework for batch correction based on variational inference and stochastic optimization of deep neural networks28. The performance of diffusion map and scVI combined with other clustering method was examined, which is worse than MNN and CCA in the three synthetic datasets (possibly due to unmet model underlying assumptions). We will explore more emerging methods in our future work.

There are several limitations of BAMM-SC. First, we filtered out genes with excessive zeros from the analysis under the assumption that lowly-expressed genes do not contribute much to clustering. This may be problematic for rare cell type identification. Second, we do not explicitly model a zero-inflation pattern, which may or may not affect clustering accuracy. A refined model that can handle inflated zeros can be further developed with a balance between computational complexity and model flexibility. Third, in our model, we assume that each cell belongs to one distinct cluster. The posterior probability measures the clustering uncertainty, which cannot be directly interpreted as a quantification of cell cycle or developmental stage. Finally, although our supervised strategy is proven to work for large datasets efficiently, it may potentially miss some rare clusters.

Our method has the potential to be extended to perform trajectory analysis29,30, and accounts for both individual and batch level heterogeneity (e.g., two individuals spread evenly across two 10x chips in a properly blocked design) by adding another level of structure. In addition, the model parameters can be used for downstream differential gene expression analysis or construct cell-type specific biomarker panels. These interesting directions are beyond the scope of this paper and will be studied in future papers. Additionally, unlike the traditional way of analyzing scRNA-seq data, BAMM-SC can be also used with batch effect correction. As shown in Supplementary Fig. 17, we ran BAMM-SC on the mouse lung dataset first and extracted cells in cluster 4. Then we applied CCA (implemented in Seurat) on this specific cluster of cells and replotted the t-SNE plot. From Supplementary Fig. 17e, cells from different samples are superimposed on each other, suggesting that most batch effect has been removed. In practice, we recommend using BAMM-SC for clustering raw count data and then use other methods, such as MNN and CCA, to remove batch effect for each individual cell type if needed.

We have applied BAMM-SC to simulated datasets and three in-house synthetic datasets to showcase its performance on different tissue types and species. With the increased popularity of population-based scRNA-seq studies, BAMM-SC will become a powerful tool for elucidating single cell level transcriptomic heterogeneity from population-based studies and a complementary approach to existing clustering methods.

## Methods

### Statistical model

We propose a Bayesian hierarchical Dirichlet multinomial mixture model to explicitly characterize different sources of variability in population scale scRNA-seq data. Specifically, let $$x_{ijl}$$ represent the number of unique UMIs for gene i in cell j from individual l ($$1 \le i \le G$$, $$1 \le j \le C_l$$, $$1 \le l \le L$$). Here, G, Cl, and L denote the total number of genes, cells (in individual l), and individuals, respectively. Our goal is to perform simultaneous clustering for cells from all L individuals. We assume that within each individual, all single cells consist of K distinct cell types. Cell type clusters are discrete, and each cell belongs to one cell type exclusively. Here, K is predefined according to prior biological knowledge, or will be estimated from the data, and K is the same among all L individuals.

Assume that $${\boldsymbol{x}}_{ \cdot {\boldsymbol{jl}}} = (x_{1jl},x_{2jl}, \ldots ,x_{Gjl})$$, the gene expression for cell j in individual l, follows a multinomial distribution multi $$\left( {T_{jl},{\boldsymbol{p}}_{ \cdot {\boldsymbol{jl}}}} \right).$$ Here, $$T_{jl} = \mathop {\sum }\limits_{i = 1}^G x_{ijl}$$ is the total number of UMIs, $${\boldsymbol{p}}_{ \cdot {\boldsymbol{jl}}} = (p_{1jl},p_{2jl}, \ldots ,p_{Gjl})$$ is the probability vector for gene expression with $$\mathop {\sum }\limits_{i = 1}^G p_{ijl} = 1$$, (where larger $$p_{ijl}$$ is associated with more UMI counts $$x_{ijl}$$). In addition, let $$z_{jl} \in \{ 1,2, \ldots ,K\}$$ represent the cell type label for cell j in individual l, where $$z_{jl} = k$$ indicates that cell j in individual l belongs to cell type k. Cells of the same cell type share a similar gene-expression pattern. If cell j in individual l belongs to cell type k ($$z_{jl} = k$$), we assume that $${\boldsymbol{p}}_{ \cdot {\boldsymbol{jl}}}$$ follows a cell-type specific Dirichlet prior Dir$$\left( {{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}} \right)$$, where $${\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}} = \left( {\alpha _{1lk},\alpha _{2lk}, \ldots ,\alpha _{Glk}} \right)$$ is the Dirichlet prior parameter for cell type k in individual l.

$$P\left( {{\boldsymbol{p}}_{.{\boldsymbol{jl}}}|z_{jl} = k,{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}} \right) = \frac{1}{{B({\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}})}}p_{1jl}^{\alpha _{1lk} - 1}p_{2jl}^{\alpha _{2lk} - 1} \ldots p_{Gjl}^{\alpha _{Glk} - 1},$$
(1)

where $$B(\alpha _{ \cdot lk})$$ is Beta function with parameter $$\alpha _{ \cdot lk} = \left( {\alpha _{1lk},\alpha _{2lk}, \ldots ,\alpha _{Glk}} \right)$$. Then after integrating $$p_{ \cdot jl}$$ out, we have:

$$P\left( {{\boldsymbol{x}}_{ \cdot {\boldsymbol{jl}}}|z_{jl} = k,{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}} \right) = \frac{{T_{jl}!}}{{\mathop {\prod }\nolimits_{i = 1}^G x_{ijl}!}}\left( {\mathop {\prod }\limits_{i = 1}^G \frac{{{\mathrm{\Gamma }}(x_{ijl} + \alpha _{ilk})}}{{{\mathrm{\Gamma }}(\alpha _{ilk})}}} \right)\frac{{{\mathrm{\Gamma }}(|{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}|)}}{{{\mathrm{\Gamma }}(T_{jl} + |{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}|)}},$$
(2)

where $$\left| {{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}} \right| = \mathop {\sum }\limits_{i = 1}^G \alpha _{ilk}$$. The joint distribution of $${\boldsymbol{x}}_{ \cdot {\boldsymbol{jl}}}$$ and $$z_{jl}$$ is

$$P\left( {{\boldsymbol{x}}_{ \cdot {\boldsymbol{jl}}},z_{jl}{\mathrm{|}}{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{l}} \cdot }} \right) = \frac{{T_{jl}!}}{{\mathop {\prod }\nolimits_{i = 1}^G x_{ijl}!}}\mathop {\sum }\limits_{k = 1}^K I(z_{jl} = k)\left( {\mathop {\prod }\limits_{i = 1}^G \frac{{{\mathrm{\Gamma }}(x_{ijl} + \alpha _{ilk})}}{{{\mathrm{\Gamma }}(\alpha _{ilk})}}} \right)\frac{{{\mathrm{\Gamma }}(|{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}|)}}{{{\mathrm{\Gamma }}\left( {T_{jl} + \left| {{\boldsymbol{\alpha }}_{ \cdot \cdot {\boldsymbol{k}}}} \right|} \right)}}.$$
(3)

We further assume that all Cl cells in individual l are independent, then the joint distribution for all cells in individual l is

$$P\left( {{\boldsymbol{x}}_{ \cdot \cdot {\boldsymbol{l}}},{\boldsymbol{z}}_{ \cdot {\boldsymbol{l}}}|{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{l}} \cdot }} \right) = \mathop {\prod }\limits_{j = 1}^{C_l} P\left( {{\boldsymbol{x}}_{ \cdot {\boldsymbol{jl}}},z_{jl}{\mathrm{|}}{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{l}} \cdot }} \right).$$
(4)

Finally, we assume that all L individuals are independent, then the overall joint distribution for all cells across all individuals becomes

$$P\left( {{\boldsymbol{x}}_{ \cdot \cdot \cdot },{\boldsymbol{z}}_{ \cdot \cdot }|{\boldsymbol{\alpha }}_{ \cdot \cdot \cdot }} \right) = \mathop {\prod }\limits_{l = 1}^L P\left( {{\boldsymbol{x}}_{ \cdot \cdot {\boldsymbol{l}}},{\boldsymbol{z}}_{ \cdot {\boldsymbol{l}}}|{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{l}}\, \cdot }} \right) \\ \propto \mathop {\prod }\limits_{l = 1}^L \mathop {\prod }\limits_{j = 1}^{C_l} \left\{ {\mathop {\sum }\limits_{k = 1}^K I\left( {z_{jl} = k} \right)\left( {\mathop {\prod }\limits_{i = 1}^G \frac{{{\mathrm{\Gamma }}\left( {x_{ijl} + \alpha _{ilk}} \right)}}{{{\mathrm{\Gamma }}\left( {\alpha _{ilk}} \right)}}} \right)\frac{{{\mathrm{\Gamma }}\left( {\left| {{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}} \right|} \right)}}{{{\mathrm{\Gamma }}\left( {T_{jl} + \left| {{\boldsymbol{\alpha }}_{ \cdot {\boldsymbol{lk}}}} \right|} \right)}}} \right\}.$$
(5)

In this model, the two sets of parameters of interest are $${\boldsymbol{z}}_{ \cdot \cdot } = \left\{ {z_{jl}} \right\}_{1 \le j \le C_l,1 \le l \le L}$$, the cell type label for cell j in individual l, and $${\boldsymbol{\alpha }}_{ \cdot \cdot \cdot } = \left\{ {\alpha _{ilk}} \right\}_{1 \le i \le G,1 \le l \le L,1 \le k \le K}$$, the Dirichlet parameters for gene i in cell type k in individual l. We adopt a full Bayesian approach and use Gibbs sampler to estimate the posterior distributions. Specifically, the joint posterior distribution for $${\boldsymbol{z}}_{ \cdot \cdot }$$ and $${\boldsymbol{\alpha }}_{ \cdot \cdot \cdot }$$ are

$$P\left( {{\boldsymbol{z}}_{ \cdot \cdot },{\boldsymbol{\alpha }}_{ \cdot \cdot \cdot }|{\boldsymbol{x}}_{ \cdot \cdot \cdot }} \right) \propto P\left( {{\boldsymbol{x}}_{ \cdot \cdot \cdot },{\boldsymbol{z}}_{ \cdot \cdot }|{\boldsymbol{\alpha }}_{ \cdot \cdot \cdot }} \right) \times Prior\left( {{\boldsymbol{\alpha }}_{ \cdot \cdot \cdot }} \right).$$
(6)

Since all α’s are strictly positive, we propose a log-normal distribution as the prior distribution for $$\alpha _{ilk}$$. We assume that for gene i in cell type k, $$\alpha _{ilk}$$ from all L individuals share the same prior distribution LN $$(\mu _{ik},\sigma _{ik}^2)$$, that is

$${\mathrm{Prior}}\left( {{\boldsymbol{\alpha }}_{{\boldsymbol{i}} \cdot {\boldsymbol{k}}}} \right) = \mathop {\prod }\limits_{l = 1}^L \frac{1}{{\alpha _{ilk}\sqrt {2\pi \sigma _{ik}^2} }}\exp \left\{ { - \frac{{\left( {\log \alpha _{ilk} - \mu _{ik}} \right)^2}}{{2\sigma _{ik}^2}}} \right\}.$$
(7)

Here, $$\mu _{ik}$$ can be estimated by the mean of $$\alpha _{ilk}$$'s: $$\hat \mu _{ik} = \frac{1}{L}\mathop {\sum }\limits_{l = 1}^L {\mathrm{log}}(\alpha _{ilk})$$. Estimation of $$\sigma _{ik}^2$$ can be challenging due to limited number of individuals. We can assume all $$\sigma _{ik}^2$$’s follow a hyper-prior: Gamma distribution Gamma$$(a_k,b_k)$$, and use information across all genes to estimate variance. In addition, we assume a noninformative prior for $$\mu _{ik}$$’s. Taken all together, we have the full posterior distribution as follows:

$$P\left( {{\boldsymbol{z}}_{ \cdot \cdot },{\boldsymbol{\alpha }}_{ \cdot \cdot \cdot }|{\boldsymbol{x}}_{ \cdot \cdot \cdot }} \right) \propto P\left( {{\boldsymbol{x}}_{ \cdot \cdot \cdot },{\boldsymbol{z}}_{ \cdot \cdot }|{\boldsymbol{\alpha }}_{ \cdot \cdot \cdot }} \right) \times \mathop {\prod }\limits_{k = 1}^K \mathop {\prod }\limits_{i = 1}^G {\mathrm{prior}}\left( {{\boldsymbol{\alpha }}_{{\boldsymbol{i}} \cdot {\boldsymbol{k}}}} \right) \times \mathop {\prod }\limits_{k = 1}^K {\mathrm{prior}}\left( {{\boldsymbol{\mu }}_{ \cdot {\boldsymbol{k}}}} \right) \times \mathop {\prod }\limits_{k = 1}^K {\mathrm{prior}}\left( {{\boldsymbol{\sigma }}_{ \cdot {\boldsymbol{k}}}^2} \right).$$
(8)

We use Gibbs sample to iteratively update $$\alpha _{ilk}$$ and $$z_{jl}$$. Details can be found in Supplementary Methods.

### Classification and computational acceleration

To further improve the computational efficiency, we provide a supervised option in BAMM-SC. Specifically, for very large-scale dataset, we use BAMM-SC to train a prediction model using a subset of cells from each individual and predict the clustering labels for the rest of cells. First, we randomly select a subset of cells from each individual and applied BAMM-SC on these selected cells. The estimate of $$\alpha _{ilk}$$ is computed as the average after deletion of the first 100 (default) iterations as burn-in. We then predict the cell type labels for other cells with realization of parameters: $$\hat \Theta = \left( {{\hat{\boldsymbol{\alpha }}}_{ \cdot 1 \cdot }, \ldots ,{\hat{\boldsymbol{\alpha }}}_{ \cdot {\boldsymbol{L}} \cdot },{\hat{\boldsymbol{\pi }}}_1, \ldots ,{\hat{\boldsymbol{\pi }}}_{\boldsymbol{L}}} \right)$$.

$$P\left( {z_{jl} = k{\mathrm{|}}{\boldsymbol{x}}_{{\boldsymbol{jl}}},\hat \Theta } \right) = \frac{{\left( {\mathop {\prod }\nolimits_{i = 1}^G \frac{{{\mathrm{\Gamma }}\left( {x_{ijl} + \hat \alpha _{ilk}} \right)}}{{{\mathrm{\Gamma }}\left( {\hat \alpha _{ilk}} \right)}}} \right)\frac{{{\mathrm{\Gamma }}\left( {|{\hat{\boldsymbol{\alpha }}}_{ \cdot {\boldsymbol{lk}}}|} \right)}}{{{\mathrm{\Gamma }}\left( {T_j + |{\hat{\boldsymbol{\alpha }}}_{ \cdot {\boldsymbol{lk}}}|} \right)}}\hat \pi _{lk}}}{{\mathop {\sum }\nolimits_{k = 1}^K \left( {\mathop {\prod }\nolimits_{i = 1}^G \frac{{{\mathrm{\Gamma }}\left( {x_{ij} + \hat \alpha _{ilk}} \right)}}{{{\mathrm{\Gamma }}\left( {\hat \alpha _{ilk}} \right)}}} \right)\frac{{{\mathrm{\Gamma }}\left( {|{\hat{\boldsymbol{\alpha }}}_{ \cdot {\boldsymbol{lk}}}|} \right)}}{{{\mathrm{\Gamma }}\left( {T_j + |{\hat{\boldsymbol{\alpha }}}_{ \cdot {\boldsymbol{lk}}}|} \right)}}\hat \pi _{lk}}}.$$
(9)

This approach can substantially reduce the computational cost for very large-scale datasets while maintaining the accuracy as shown in Supplementary Fig. 14.

### Single-cell sequencing library construction

10× Genomics Chromium system, which is a microfluidics platform based on Gel bead in EMulsion (GEM) technology, was used for generating real test datasets. Cells mixed with reverse transcription reagents were loaded into the Chromium instrument. This instrument separated cells into minireaction partitions formed by oil microdroplets, each containing a gel bead and a cell, known as GEMs. GEMs contain a gel bead, scaffold for an oligonucleotide that is composed of an oligo-dT section for priming reverse transcription, and barcodes for each cell and each transcript as described. GEM generation takes place in a multiple-channel microfluidic chip that encapsulates single-gel beads. Reverse transcription takes place inside each droplet. Approximately, 1000-fold excess of partitions compared to cells ensured low capture of duplicate cells. The reaction mixture/emulsion was removed from the Chromium instrument, and reverse transcription was performed. The emulsion was then broken using a recovery agent, and following Dynabead and SPRI clean up cDNAs were amplified by PCR (C1000, Bio-Rad). cDNAs were sheared (Covaris) into ~200 bp length. DNA fragment ends were repaired, A-tailed and adapters ligated. The library was quantified using KAPA Universal Library Quantification Kit KK4824 and further characterized for cDNA length on a Bioanalyzer using a High Sensitivity DNA kit. All sequencing experiments were conducted using Illumina NextSeq 500 in the Genomics Sequencing Core at the University of Pittsburgh.

### Data description

Human PBMC dataset: Under a protocol approved by the University of Pittsburgh Institutional Review Board, peripheral blood was obtained from healthy donors by venipuncture. Each subject gave written informed consent. PBMC were isolated from whole blood by density gradient centrifugation using Ficoll–Hypaque. PBMC were then counted and resuspended in phosphate buffered saline with 0.04% bovinue serum albumin, and were processed through the Chromium 10× Controller according to the manufacturers’ instructions, targeting a recovery of ~2000 cells. The following steps were all performed under the aforementioned protocol developed by 10× Genomics.

Human skin dataset: Skin samples were obtained by performing 3 mm punch biopsies from the dorsal midforearm of healthy control subjects after informed consent under a protocol approved by the University of Pittsburgh Institutional Review Board. Skin for scRNA-seq was digested enzymatically (Miltenyi Biotec Whole Skin Dissociation Kit, human) for 2 h and further dispersed using the Miltenyi gentleMACS Octo Dissociator. The resulting cell suspension was filtered through 70 micron cell strainers twice and re-suspended in phosphate-buffered saline containing 0.04% bovine serum albumin. Cells from biopsies were mixed with reverse transcription reagents then loaded into the Chromium instrument (10× Genomics). Totally, ~2600–4300 cells were loaded into the instrument to obtain data on ~1100–1800 cells, anticipating a multiplet rate of ~1.2% of partitions. The following steps were all performed under the aforementioned protocol developed by 10× Genomics.

Mouse lung dataset: Lung single cell suspension from naïve and infected C57BL/6 mice were subject to scRNA-seq library preparation protocol. Briefly, left lobs of both naïve and infected mice were removed and digested by Collagenase/DNase to obtain single-cell suspension. Mononuclear cells after filtration with a 40 μM cell strainer were separated into minireaction partitions or GEMs formed by oil microdroplets, each containing a gel bead and a cell, by the Chromium instrument (10× Genomics). The reaction mixture/emulsion with captured and barcoded mRNAs were removed from the Chromium instrument followed by reverse transcription. The cDNA samples were fragmented and amplified using the Nextera XT kit (Illumina). The following steps were all performed under aforementioned the protocol developed by 10× Genomics. We have complied with all relevant ethical regulations for animal research. The animal protocol was approved by the University of Pittsburgh Institutional Animal Care and Use Committee.

### Reporting summary

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

## Data availability

The study uses various publicly available scRNA-seq datasets. Both human PBMC (sample 5) and purified CD19+B cell scRNA-seq data that support the findings of this study are available at https://support.10xgenomics.com/single-cell-gene-expression/datasets. The raw fastq files and preprocessed experimental test datasets (human PBMCs, mouse lung and human skin tissues) have been deposited in the gene expression omnibus (GEO) database under accession number GSE128066. All other relevant data are available upon request.

## Code availability

BAMM-SC, including all source and example code, is freely available as an R package with a detailed tutorial at https://github.com/CHPGenetics/BAMMSC.

Journal peer review information: Nature Communications thanks the anonymous reviewer(s) for their contribution to the peer review of this work.

Publisher’s note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## References

1. 1.

Gawad, C., Koh, W. & Quake, S. R. Single-cell genome sequencing: current state of the science. Nat. Rev. Genet. 17, 175–188 (2016).

2. 2.

Tang, F. et al. mRNA-Seq whole-transcriptome analysis of a single cell. Nat. Methods 6, 377–382 (2009).

3. 3.

Macosko, E. Z. et al. Highly parallel genome-wide expression profiling of individual cells using nanoliter droplets. Cell 161, 1202–1214 (2015).

4. 4.

Zheng, G. X. et al. Massively parallel digital transcriptional profiling of single cells. Nat. Commun. 8, 14049 (2017).

5. 5.

Jaitin, D. A. et al. Massively parallel single-cell RNA-seq for marker-free decomposition of tissues into cell types. Science 343, 776–779 (2014).

6. 6.

Pollen, A. A. et al. Low-coverage single-cell mRNA sequencing reveals cellular heterogeneity and activated signaling pathways in developing cerebral cortex. Nat. Biotechnol. 32, 1053–1058 (2014).

7. 7.

van der Wijst, M. G. P. et al. Single-cell RNA sequencing identifies celltype-specific cis-eQTLs and co-expression QTLs. Nat. Genet. 50, 493–497 (2018).

8. 8.

Rodriguez, A. & Laio, A. Machine learning. Clustering by fast search and find of density peaks. Science 344, 1492–1496 (2014).

9. 9.

Wang, B. et al. SIMLR: a tool for large-scale genomic analyses by multi-kernel learning. Proteomics 18 1700232 (2018).

10. 10.

duVerle, D. A., Yotsukura, S., Nomura, S., Aburatani, H. & Tsuda, K. CellTree: an R/bioconductor package to infer the hierarchical structure of cell populations from single-cell RNA-seq data. BMC Bioinformatics 17, 363 (2016).

11. 11.

Kiselev, V. Y. et al. SC3: consensus clustering of single-cell RNA-seq data. Nat. Methods 14, 483–486 (2017).

12. 12.

Ji, Z. & Ji, H. TSCAN: pseudo-time reconstruction and evaluation in single-cell RNA-seq analysis. Nucleic Acids Res. 44, e117 (2016).

13. 13.

Sun, Z. et al. DIMM-SC: a Dirichlet mixture model for clustering droplet-based single cell transcriptomic data. Bioinformatics 34, 139–146 (2018).

14. 14.

Crow, M., Paul, A., Ballouz, S., Huang, Z. J. & Gillis, J. Characterizing the replicability of cell types defined by single cell RNA-sequencing data using MetaNeighbor. Nat. Commun. 9, 884 (2018).

15. 15.

Spitzer, M. H. et al. IMMUNOLOGY. An interactive reference framework for modeling a dynamic immune system. Science 349, 1259425 (2015).

16. 16.

Haghverdi, L., Lun, A. T. L., Morgan, M. D. & Marioni, J. C. Batch effects in single-cell RNA-sequencing data are corrected by matching mutual nearest neighbors. Nat. Biotechnol. 36, 421–427 (2018).

17. 17.

Satija, R., Farrell, J. A., Gennert, D., Schier, A. F. & Regev, A. Spatial reconstruction of single-cell gene expression data. Nat. Biotechnol. 33, 495–502 (2015).

18. 18.

Rand, W. M. Objective criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66, 846–850 (1971).

19. 19.

Freytag, S., Tian, L., Lonnstedt, I., Ng, M. & Bahlo, M. Comparison of clustering tools in R for medium-sized 10x Genomics single-cell RNA-sequencing data. F1000Res. 7, 1297 (2018).

20. 20.

Duo, A., Robinson, M. D. & Soneson, C. A systematic performance evaluation of clustering methods for single-cell RNA-seq data. F1000Res. 7, 1141 (2018).

21. 21.

Zappia, L., Phipson, B. & Oshlack, A. Splatter: simulation of single-cell RNA sequencing data. Genome. Biol. 18, 174 (2017).

22. 22.

Chen, K. & Kolls, J. K. T cell-mediated host immune defenses in the lung. Annu. Rev. Immunol. 31, 605–633 (2013).

23. 23.

Weiser, J. N. The pneumococcus: why a commensal misbehaves. J. Mol. Med. 88, 97–102 (2010).

24. 24.

Tabib, T., Morse, C., Wang, T., Chen, W. & Lafyatis, R. SFRP2/DPP4 and FMO1/LSP1 define major fibroblast populations in human skin. J. Invest. Dermatol. 138, 802–810 (2018).

25. 25.

Datta, S. & Datta, S. Comparisons and validation of statistical clustering techniques for microarray gene expression data. Bioinformatics 19, 459–466 (2003).

26. 26.

Rousseeuw, P. J. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 20, 53–65 (1987).

27. 27.

Coifman, R. R. et al. Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps. Proc. Natl Acad. Sci. USA 102, 7426–7431 (2005).

28. 28.

Lopez, R., Regier, J., Cole, M. B., Jordan, M. I. & Yosef, N. Deep generative modeling for single-cell transcriptomics. Nat. Methods 15, 1053 (2018).

29. 29.

Trapnell, C. et al. The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells. Nat. Biotechnol. 32, 381–386 (2014).

30. 30.

Trapnell, C. Defining cell types and states with single-cell genomics. Genome Res. 25, 1491–1498 (2015).

## Acknowledgements

This work is supported by National Institute of Health grants R56HL137709 (K.C.), P50 CA097190 and P30 CA047904 (D.A.A.V.), P50 AR060780 (R.L. and W.C.), R35HL139930 (J.K.), and Children’s Hospital of Pittsburgh (W.C. and Z.S.).

## Author information

### Author notes

1. These authors contributed equally: Zhe Sun, Li Chen.

### Affiliations

1. #### Department of Biostatistics, Graduate School of Public Health, University of Pittsburgh, Pittsburgh, PA, 15261, USA

• Zhe Sun
• , Ying Ding
•  & Wei Chen

• Li Chen
3. #### Division of Pulmonary Medicine, Department of Pediatrics, Children’s Hospital of Pittsburgh of UPMC, University of Pittsburgh, Pittsburgh, PA, 15224, USA

• Hongyi Xin
• , Yale Jiang
•  & Wei Chen

• Yale Jiang
5. #### Department of Biostatistics, School of Public Health, University of Michigan, Ann Arbor, MI, 48109, USA

• Qianhui Huang
6. #### Department of Immunology, School of Medicine, University of Pittsburgh, Pittsburgh, PA, 15262, USA

• Anthony R. Cillo
• , Tullia C. Bruno
•  & Dario A. A. Vignali
7. #### Division of Rheumatology and Clinical Immunology, Department of Medicine, School of Medicine, University of Pittsburgh, Pittsburgh, PA, 15261, USA

• Tracy Tabib
•  & Robert Lafyatis
8. #### School of Medicine, Tulane University, New Orleans, LA, 70112, USA

• Jay K. Kolls
9. #### Tumor Microenvironment Center, UPMC Hillman Cancer Center, Pittsburgh, PA, 15232, USA

• Tullia C. Bruno
•  & Dario A. A. Vignali
10. #### Cancer Immunology and Immunotherapy Program, UPMC Hillman Cancer Center, Pittsburgh, PA, 15232, USA

• Dario A. A. Vignali

• Kong Chen

• Ming Hu

### Contributions

M.H. and W.C. conceived the study; Z.S. led the statistical modeling and data analysis; L.C. helped with developing the R package; A.R.C., T.C.B., and D.A.A.V. performed the experiments for the human PBMC data; T.T. and R.L. performed the experiments for the human skin data; K.C. and J.K.K. performed the experiments for the mouse data; H.X., Y.J., and Q.H. helped with the preprocessing and analyzing the data; Y.D., W.C., and M.H. supervised the research; and Z.S., W.C., Y.D., and M.H. led the writing of the paper with input from all the other authors.

### Competing interests

The authors declare no competing interests.

### Corresponding authors

Correspondence to Ying Ding or Ming Hu or Wei Chen.


text:
GMAT Question of the Day - Daily to your Mailbox; hard ones only

 It is currently 19 Feb 2019, 13:39

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

## Events & Promotions

###### Events & Promotions in February
PrevNext
SuMoTuWeThFrSa
272829303112
3456789
10111213141516
17181920212223
242526272812
Open Detailed Calendar
• ### Free GMAT Prep Hour

February 20, 2019

February 20, 2019

08:00 PM EST

09:00 PM EST

Strategies and techniques for approaching featured GMAT topics. Wednesday, February 20th at 8 PM EST
• ### Online GMAT boot camp for FREE

February 21, 2019

February 21, 2019

10:00 PM PST

11:00 PM PST

Kick off your 2019 GMAT prep with a free 7-day boot camp that includes free online lessons, webinars, and a full GMAT course access. Limited for the first 99 registrants! Feb. 21st until the 27th.

# 46, 47, 48, 49, 50, 51, 52, 53, 54 The standard deviation of the 9 nu

 new topic post reply Question banks Downloads My Bookmarks Reviews Important topics
Author Message
TAGS:

### Hide Tags

Math Revolution GMAT Instructor
Joined: 16 Aug 2015
Posts: 6966
GMAT 1: 760 Q51 V42
GPA: 3.82
46, 47, 48, 49, 50, 51, 52, 53, 54 The standard deviation of the 9 nu  [#permalink]

### Show Tags

17 Dec 2017, 23:31
00:00

Difficulty:

35% (medium)

Question Stats:

67% (01:16) correct 33% (01:41) wrong based on 65 sessions

### HideShow timer Statistics

[GMAT math practice question]

$$46, 47, 48, 49, 50, 51, 52, 53, 54$$
The standard deviation of the $$9$$ numbers in the above list lies between $$2$$ and $$3$$. How many of the $$9$$ numbers are within one standard deviation of the average (arithmetic mean)?

A. $$5$$
B. $$6$$
C. $$7$$
D. $$8$$
E. $$9$$

_________________

MathRevolution: Finish GMAT Quant Section with 10 minutes to spare
The one-and-only World’s First Variable Approach for DS and IVY Approach for PS with ease, speed and accuracy.
"Only $149 for 3 month Online Course" "Free Resources-30 day online access & Diagnostic Test" "Unlimited Access to over 120 free video lessons - try it yourself" Intern Joined: 27 Mar 2016 Posts: 13 Location: India Schools: IIM (S) GMAT 1: 590 Q49 V21 GPA: 3.9 Re: 46, 47, 48, 49, 50, 51, 52, 53, 54 The standard deviation of the 9 nu [#permalink] ### Show Tags 18 Dec 2017, 06:35 Although I have marked the correct answer, I just want to confirm my approach. I have calculated s.d of the series 48,49, 50,51,52 (sqrt2.5) and 47,48,49,50,51,52,53(sqrt7) Please correct me whether my approach is correct. Retired Moderator Joined: 25 Feb 2013 Posts: 1216 Location: India GPA: 3.82 46, 47, 48, 49, 50, 51, 52, 53, 54 The standard deviation of the 9 nu [#permalink] ### Show Tags 18 Dec 2017, 09:12 1 MathRevolution wrote: [GMAT math practice question] $$46, 47, 48, 49, 50, 51, 52, 53, 54$$ The standard deviation of the $$9$$ numbers in the above list lies between $$2$$ and $$3$$. How many of the $$9$$ numbers are within one standard deviation of the average (arithmetic mean)? A. $$5$$ B. $$6$$ C. $$7$$ D. $$8$$ E. $$9$$ The mean of the above set is the middle value $$= 50$$ $$2<SD<3$$, as $$1 SD = 1*SD$$ so one $$SD$$ will also be between $$2$$ and $$3$$. SD will be $$2.nnn$$ (2.something). for the sake of calculation let $$SD = 2.5$$ lower limit: $$Mean - S.D = 50 - 2.5 = 47.5$$ upper limit: $$Mean + S.D = 50 + 2.5 = 52.5$$ So numbers lying within 1 $$SD$$ will range from $$48$$ to $$52$$ which are 48, 49, 50, 51 & 52 $$=5$$ Option A Retired Moderator Joined: 25 Feb 2013 Posts: 1216 Location: India GPA: 3.82 Re: 46, 47, 48, 49, 50, 51, 52, 53, 54 The standard deviation of the 9 nu [#permalink] ### Show Tags 18 Dec 2017, 09:14 ushasi wrote: Although I have marked the correct answer, I just want to confirm my approach. I have calculated s.d of the series 48,49, 50,51,52 (sqrt2.5) and 47,48,49,50,51,52,53(sqrt7) Please correct me whether my approach is correct. Hi ushasi Could not get your approach. Can you explain your reason for calculating SD for two different sets as mentioned by you? Intern Joined: 10 Dec 2017 Posts: 3 Re: 46, 47, 48, 49, 50, 51, 52, 53, 54 The standard deviation of the 9 nu [#permalink] ### Show Tags 18 Dec 2017, 10:25 MathRevolution wrote: [GMAT math practice question] $$46, 47, 48, 49, 50, 51, 52, 53, 54$$ The standard deviation of the $$9$$ numbers in the above list lies between $$2$$ and $$3$$. How many of the $$9$$ numbers are within one standard deviation of the average (arithmetic mean)? A. $$5$$ B. $$6$$ C. $$7$$ D. $$8$$ E. $$9$$ Solution: 1.The standard deviation of 9 numbers lies between 2 and 3 2. considering standard deviation 2.5 approx. . 3. Mean of the above 9 numbers is 50. 4.Hence numbers lying between Mean + (1 Standard deviation ) = 52.5 and Mean - (1 Standard deviation) = 47.5 are 48,49,50,51 and 52 5. Hence 5 numbers are lying within 1 standard deviation from the Mean. Hence answer is A _________________ Regards, Sneha Tatavarthy Math Facilitator International Baccalaureate Math Revolution GMAT Instructor Joined: 16 Aug 2015 Posts: 6966 GMAT 1: 760 Q51 V42 GPA: 3.82 Re: 46, 47, 48, 49, 50, 51, 52, 53, 54 The standard deviation of the 9 nu [#permalink] ### Show Tags 20 Dec 2017, 01:00 => The average of the $$9$$ numbers is $$50$$. So, if n lies within one standard deviation of the mean, then $$50 – 2.xxx < n < 50 + 2.xxx$$ $$47.xxx < n < 52.xxx$$ and $$n = 48, 49, 50, 51, or 52.$$ There are five numbers in this range. Therefore, the answer is A. Answer : A _________________ MathRevolution: Finish GMAT Quant Section with 10 minutes to spare The one-and-only World’s First Variable Approach for DS and IVY Approach for PS with ease, speed and accuracy. "Only$149 for 3 month Online Course"
"Free Resources-30 day online access & Diagnostic Test"
"Unlimited Access to over 120 free video lessons - try it yourself"

Re: 46, 47, 48, 49, 50, 51, 52, 53, 54 The standard deviation of the 9 nu   [#permalink] 20 Dec 2017, 01:00
Display posts from previous: Sort by

# 46, 47, 48, 49, 50, 51, 52, 53, 54 The standard deviation of the 9 nu

 new topic post reply Question banks Downloads My Bookmarks Reviews Important topics

 Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.


text:
mersenneforum.org mtsieve
 Register FAQ Search Today's Posts Mark Forums Read

 2022-05-17, 14:13 #628 rogue     "Mark" Apr 2003 Between here and the 23·3·52·11 Posts I tried switching to the cygwin g++ compiler, but it won't link. It appears to be a bug in primesieve or the linker or compiler used by cygwin. So I am now trying to use the llvm-mingw compiler. It appears that I can debug with lldb or gdb for programs built on it. This will require a bit of testing. It seems to crash when resetting the rounding mode for SSE, but only one sieve uses SSE, so I will probably just modify that sieve to use different logic and thus remove SSE assembler completely from the code. It is possible that something else I changed between releases triggered this crash, but it is odd that only srsieve2 seems to be affected by it. Without use of gdb on msys2 builds, I cannot diagnose the root cause of the crash.
 2022-05-23, 13:30 #629 ryanp     Jun 2012 Boulder, CO 383 Posts Found what seems to be a bug in the latest SVN code. I have not had time to recompile or test with gdb. Code: $./srsieve2 -P 1e14 -W 64 -s "39*2^n+1" -o ferm39_10M_20M_sv1e14.txt -n 10e6 -N 20e6 srsieve2 v1.6.2, a program to find factors of k*b^n+c numbers for fixed b and variable k and n Sieving with generic logic for p >= 3 Sieve started: 3 < p < 1e14 with 10000001 terms (10000000 < n < 20000000, k*2^n+1) (expecting 9659200 factors) Sieving with single sequence c=1 logic for p >= 257 BASE_MULTIPLE = 30, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720 Split 1 base 2 sequence into 408 base 2^720 sequences. Legendre summary: Approximately 40 B needed for Legendre tables 1 total sequences 1 are eligible for Legendre tables 0 are not eligible for Legendre tables 1 have Legendre tables in memory 0 cannot have Legendre tables in memory 0 have Legendre tables loaded from files 1 required building of the Legendre tables 518400 bytes used for congruent q and ladder indices 311200 bytes used for congruent qs and ladders Unable to lock mutex thread_6_worker. Exiting. Interestingly, this only seems to happen for 39*2^n+1 and not 37*2^n+1 or 41*2^n+1. Last fiddled with by ryanp on 2022-05-23 at 13:31 Reason: added some details 2022-05-23, 15:00 #630 rogue "Mark" Apr 2003 Between here and the 23×3×52×11 Posts Quote:  Originally Posted by ryanp Found what seems to be a bug in the latest SVN code. I have not had time to recompile or test with gdb. Code: $ ./srsieve2 -P 1e14 -W 64 -s "39*2^n+1" -o ferm39_10M_20M_sv1e14.txt -n 10e6 -N 20e6 srsieve2 v1.6.2, a program to find factors of k*b^n+c numbers for fixed b and variable k and n Sieving with generic logic for p >= 3 Sieve started: 3 < p < 1e14 with 10000001 terms (10000000 < n < 20000000, k*2^n+1) (expecting 9659200 factors) Sieving with single sequence c=1 logic for p >= 257 BASE_MULTIPLE = 30, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720 Split 1 base 2 sequence into 408 base 2^720 sequences. Legendre summary: Approximately 40 B needed for Legendre tables 1 total sequences 1 are eligible for Legendre tables 0 are not eligible for Legendre tables 1 have Legendre tables in memory 0 cannot have Legendre tables in memory 0 have Legendre tables loaded from files 1 required building of the Legendre tables 518400 bytes used for congruent q and ladder indices 311200 bytes used for congruent qs and ladders Unable to lock mutex thread_6_worker. Exiting. Interestingly, this only seems to happen for 39*2^n+1 and not 37*2^n+1 or 41*2^n+1.
srsieve2 doesn't seem to perform nicely for large numbers of threads. I think it would require a rethinking of the framework to do that. You are probably off running multiple instances with a smaller number of threads, each with its own range. You can also bump -w to change the number of primes per worker thread. That might alleviate some of the thread contention. I do not have a CPU with more than 8 cores to run a test like this on.

I do not recall if sr1sieve is faster (compared to srsieve2). I know it is slower than srsieve2cl.

Last fiddled with by rogue on 2022-05-23 at 15:13

2022-05-23, 17:16   #631
ryanp

Jun 2012
Boulder, CO

17F16 Posts

Quote:
 Originally Posted by rogue srsieve2 doesn't seem to perform nicely for large numbers of threads. I think it would require a rethinking of the framework to do that. You are probably off running multiple instances with a smaller number of threads, each with its own range. You can also bump -w to change the number of primes per worker thread. That might alleviate some of the thread contention. I do not have a CPU with more than 8 cores to run a test like this on. I do not recall if sr1sieve is faster (compared to srsieve2). I know it is slower than srsieve2cl.
I've been able to repro this on multiple machines. Observations:

* it fails consistently and only with -s "39*2^n+1"
* it fails with even -W 4, though this produces:

Code:
518400 bytes used for congruent q and ladder indices
311200 bytes used for congruent qs and ladders
corrupted size vs. prev_size
Aborted

Code:
518400 bytes used for congruent q and ladder indices
311200 bytes used for congruent qs and ladders
Aborted
Here's the result of debugging with gdb:

Code:
[New Thread 0x7ffff6ef9640 (LWP 206359)]
corrupted size vs. prev_size

__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:49
49	../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) bt
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:49
#1  0x00007ffff7a4a546 in __GI_abort () at abort.c:79
#2  0x00007ffff7aa1eb8 in __libc_message (action=action@entry=do_abort,
fmt=fmt@entry=0x7ffff7bbfa78 "%s\n") at ../sysdeps/posix/libc_fatal.c:155
#3  0x00007ffff7aa991a in malloc_printerr (
str=str@entry=0x7ffff7bbd714 "corrupted size vs. prev_size")
at malloc.c:5628
av=<optimized out>) at malloc.c:1608
av=av@entry=0x7ffff7bf6ba0 <main_arena>, bytes=bytes@entry=112)
at malloc.c:4263
#6  0x00007ffff7aae4b1 in __GI___libc_malloc (bytes=112) at malloc.c:3237
#7  0x00007ffff7e0e6bc in operator new(unsigned long) ()
from /lib/x86_64-linux-gnu/libstdc++.so.6
#8  0x000055555556f308 in __gnu_cxx::new_allocator<primesieve::SievingPrime>::allocate (this=0x7fffffffd5f0, __n=14)
at /usr/include/c++/11/ext/new_allocator.h:127
#9  0x000055555556efb2 in std::allocator_traits<std::allocator<primesieve::SievingPrime> >::allocate (__a=..., __n=14)
at /usr/include/c++/11/bits/alloc_traits.h:464
#10 0x000055555556ea3c in std::_Vector_base<primesieve::SievingPrime, std::allocator<primesieve::SievingPrime> >::_M_allocate (this=0x7fffffffd5f0, __n=14)
at /usr/include/c++/11/bits/stl_vector.h:346
#11 0x000055555556e6c4 in std::vector<primesieve::SievingPrime, std::allocator<primesieve::SievingPrime> >::reserve (this=0x7fffffffd5f0, __n=14)
at /usr/include/c++/11/bits/vector.tcc:78
#12 0x000055555556ba1c in primesieve::EratSmall::init (this=0x7fffffffd5d0,
stop=1021020, l1CacheSize=17017, maxPrime=17) at sieve/EratSmall.cpp:57
#13 0x000055555556f9d4 in primesieve::PreSieve::initBuffer (
this=0x55555583efd8, maxPrime=17, primeProduct=510510)
at sieve/PreSieve.cpp:86
#14 0x000055555556f8dc in primesieve::PreSieve::init (this=0x55555583efd8,
start=11924379, stop=23704475) at sieve/PreSieve.cpp:68
#15 0x0000555555564079 in primesieve::Erat::init (this=0x55555583ec70,
start=11924379, stop=23704475, sieveSize=512, preSieve=...)
at sieve/Erat.cpp:79
#16 0x000055555557793b in primesieve::PrimeGenerator::initErat (
this=0x55555583ec70) at sieve/PrimeGenerator.cpp:159
this=0x55555583ec70,
primes=std::vector of length 256, capacity 256 = {...},
size=0x7fffffffd8f8) at sieve/PrimeGenerator.cpp:147
#18 0x0000555555577bab in primesieve::PrimeGenerator::sieveSegment (
this=0x55555583ec70,
primes=std::vector of length 256, capacity 256 = {...},
size=0x7fffffffd8f8) at sieve/PrimeGenerator.cpp:232
#19 0x0000555555577d56 in primesieve::PrimeGenerator::fill (
this=0x55555583ec70,
primes=std::vector of length 256, capacity 256 = {...},
size=0x7fffffffd8f8) at sieve/PrimeGenerator.cpp:291
#20 0x00005555555850d5 in primesieve::iterator::generate_next_primes (
this=0x7fffffffd8f0) at sieve/iterator.cpp:67
#21 0x0000555555560110 in primesieve::iterator::next_prime (
this=0x7fffffffd8f0) at sieve/primesieve/iterator.hpp:69
#22 0x0000555555560632 in primesieve::store_n_primes<std::vector<unsigned long, std::allocator<unsigned long> > > (n=216804, start=1257,
primes=std::vector of length 783196, capacity 1000000 = {...})
at sieve/primesieve/StorePrimes.hpp:87
#23 0x000055555556028c in primesieve::generate_n_primes<unsigned long> (
n=1000000, start=1258, primes=0x5555556fb390)
at core/../sieve/primesieve.hpp:62
#24 0x0000555555561fff in Worker::ProcessNextPrimeChunk (this=0x5555556fb380,
startFrom=1257, maxPrimeForChunk=1257) at core/Worker.cpp:155
#25 0x000055555555cbe1 in App::Sieve (this=0x5555555d98e0) at core/App.cpp:450
#26 0x000055555555ca3b in App::Run (this=0x5555555d98e0) at core/App.cpp:405
#27 0x0000555555563288 in main (argc=13, argv=0x7fffffffdba8)
at core/main.cpp:87`

Last fiddled with by ryanp on 2022-05-23 at 17:18 Reason: add gdb backtrace

 2022-05-23, 18:15 #632 pepi37     Dec 2011 After milion nines:) 72·31 Posts What is range of n? [QUOTE=ryanp;606344]I've been able to repro this on multiple machines. Observations: * it fails consistently and only with -s "39*2^n+1" * it fails with even -W 4, though this produces: [ Last fiddled with by pepi37 on 2022-05-23 at 18:48
 2022-05-23, 19:29 #633 rogue     "Mark" Apr 2003 Between here and the 147108 Posts When I have some time I will play around with this using the latest build as it uses a different compiler. I have also upgraded to the latest primesieve code. One of those changes might fix this issue.
 2022-05-23, 21:58 #634 pepi37     Dec 2011 After milion nines:) 27578 Posts fix for problem (temporary) Make initial sieve with srsieve use srsieve2 version 1.5.3 working on 6 core CPU without problem srsieve2 -P 1446900638801 -W 6 -w5e6 -i a.txt -o b.txt -O fact39.txt srsieve2 v1.5.3, a program to find factors of k*b^n+c numbers for fixed b and variable k and n Sieving with generic logic for p >= 100000000 Split 1 base 2 sequence into 204 base 2^360 sequences. 712822 bytes used for congruence tables 522 bytes used for Legendre tables Sieve started: 1e8 < p < 1446900638801 with 1353444 terms (11924391 < n < 23704473, k*2^n+1) (expecting 463052 factors) p=731561923, 679.7K p/sec, 142804 factors found at 476.8 f/sec (last 1 min), 0.0% done. ETC 2022-05-25 14:45
2022-05-23, 22:00   #635
pepi37

Dec 2011
After milion nines:)

5EF16 Posts

Quote:
 Originally Posted by rogue srsieve2 doesn't seem to perform nicely for large numbers of threads. I think it would require a rethinking of the framework to do that. You are probably off running multiple instances with a smaller number of threads, each with its own range. You can also bump -w to change the number of primes per worker thread. That might alleviate some of the thread contention. I do not have a CPU with more than 8 cores to run a test like this on. I do not recall if sr1sieve is faster (compared to srsieve2). I know it is slower than srsieve2cl.

I noticed this on 12 core Ryzen ( HT is off) When I set 12 cores I only have 785% CPU utilization ( Linux)

All times are UTC. The time now is 04:51.

Tue May 24 04:51:54 UTC 2022 up 40 days, 2:53, 0 users, load averages: 1.45, 1.18, 1.14


text:
# Michael Francis Atiyah

## 1 Michael Francis Atiyah

British mathematician,
Born: April 22nd, 1929 in London, UK

### 1.1 Education:

• High school education was partly at Victoria College, in Cairo, Egypt, and partly in Manchester, UK, at the Manchester Grammar School

• BA, at Trinity College, in Cambridge, UK

• MA (doctorate) at Trinity College, in Cambridge, UK in 1954

• Commonwealth Fellow at the Institute for Advanced Study in Princeton, USA, in 1955

• College Lecturer in Cambridge, UK, in 1957

• Active Fellow of Pembroke College in Cambridge, UK, 1958-1961.

• Reader at the University of Oxford and Fellow of St Catherine’s College.

• Savilian Chair of Geometry at Oxford, 1963-1969

• Professor of Mathematics at the Institute for Advanced Study in Princeton, USA in 1969

• Royal Society Research Professor at Oxford in 1972

### 1.2 Major Fields of Research: Topology, $K$-Theory and TQFT Foundations

• Michael Atiyah has contributed to a wide range of topics in mathematics centering around the interaction between geometry and analysis. His first major contribution (in collaboration with F. Hirzebruch) was the development of a new and powerful technique in topology ($K$-theory) which led to the solution of many outstanding difficult problems. Subsequently (in collaboration with I. M. Singer) he established an important theorem dealing with the number of solutions of elliptic differential equations. This ‘index theorem’ had antecedents in algebraic geometry and led to important new links between differential geometry, topology and analysis. Combined with considerations of symmetry it led (jointly with Raoul Bott) to a new and refined fixed point theorem’ with wide applicability.;”

• “The K-theory and the index theorem are studied in Atiyah’s book entitled ‘$K$-theory’ (1967, reprinted 1989) and his joint work with G. B. Segal, “The Index of Elliptic Operators I-V” in Annals of Mathematics, volumes 88 and 93 (1968, 1971). Atiyah also described his work on the index theorem in “The index of elliptic operators” given as an American Mathematical Society Colloquium Lecture in 1973.”

• The index theorem could be interpreted in terms of quantum theory and has proved a useful tool for theoretical physicists. Beyond these linear problems, gauge theories involved deep and interesting nonlinear differential equations. In particular, the Yang-Mills equations have turned out to be particularly fruitful for mathematicians. Atiyah initiated much of the early work in this field and his student Simon Donaldson went on to make spectacular use of these ideas in 4-dimensional geometry. More recently Atiyah has been influential in stressing the role of topology in quantum field theory”…(more specifically in TQFT)…“ and in bringing the work of theoretical physicists, notably E Witten, to the attention of the mathematical community.”

• The theories of superspace and supergravity and the string theory of fundamental particles, that involve the theory of Riemann surfaces in novel and unexpected ways, were all areas of theoretical physics which developed using” …some of the ideas which Atiyah introduced.

### 1.3 Honours awarded to Michael Francis Atiyah:

• Foreign member of several academies including those of: the United States, Sweden, Germany, France, Ireland, India, Australia, China, Russia and the Ukraine.

• Fellow of the Royal Society of London in 1962 at the age of 32

• British Mathematical Colloquium morning speaker 1957, 1962

• LMS Berwick Prize winner 1961

• Speaker at International Congress 1966

• Royal Medal of the Society in 1968

• American Mathematical Society Colloquium Lecturer in 1973

• Royal Society’s Bakerian Lecture on Global geometry in 1975

• President of the London Mathematical Society in 1974-76

• Honorary Fellow of the Edinburgh Maths Society 1979

• De Morgan Medal in 1980

• Feltrinelli Prize from the Accademia Nazionale dei Lincei in 1981

• He was Knighted by Queen Elizabeth II in 1983

• Fellow of the Royal Society of Edinburgh 1985

• King Faisal International Prize for Science in 1987

• Copley Medal in 1988

• AMS Gibbs Lecturer 1991

• Member of the Order of Merit in 1992

• Hedrick lecturer 1993

• President of the Royal Society, 1990 to 1995

• Abel Prize 2004

• Honorary Degrees from: Bonn, Warwick, Durham, St Andrews, Dublin, Chicago, Edinburgh, Cambridge, Essex, London, Sussex, Ghent, Reading, Helsinki, Leicester, Rutgers, Salamanca, Montreal, Waterloo, Wales, Queen’s-Kingston, Keele, Birmingham, Lebanon and the Open University.

Suggested further reading: an article by http://www-groups.dcs.st-and.ac.uk/ history/Biographies/Atiyah.htmlJ. J. O’Connor and E F Robertson

### 1.4 Other Articles about M.F. Atiyah:

M Atiyah, Address of the president, Sir Michael Atiyah, given at the anniversary meeting on 29 November 1991, Notes and Records Roy. Soc. London 46 (1) (1992), 155-169. M Atiyah, Address of the President, Sir Michael Atiyah, O. M., given at the anniversary meeting on 30 November 1994, Notes and Records Roy. Soc. London 49 (1) (1995), 141-151. Michael F Atiyah, in M Atiyah and D Iagolnitzer (eds.), Fields Medalists Lectures (Singapore, 1997), 113-114. H Cartan, L’oeuvre de Michael F Atiyah, Proceedings of the International Congress of Mathematicians, Moscow, 1966 (Moscow, 1968). E Getzler, The Atiyah-Bott fixed point formula, in Raoul Bott: collected papers 2 (Boston, MA, 1994), xxxi-xxxiii. R Minio, An interview with Michael Atiyah (Czech), Pokroky Mat. Fyz. Astronom. 31 (3) (1986), 154-168. R Minio, An interview with Michael Atiyah (Slovenian), Obzornik Mat. Fiz. 31 (5-6) (1984), 129-142. R Minio, An interview with Michael Atiyah, Math. Intelligencer 6 (1) (1984), 9-19.

Title Michael Francis Atiyah MichaelFrancisAtiyah 2013-03-22 18:26:53 2013-03-22 18:26:53 bci1 (20947) bci1 (20947) 16 bci1 (20947) Biography msc 12-00 msc 11S70 msc 11R70 msc 00-02


text:
# Book:J.C. Burkill/A Second Course in Mathematical Analysis

## J.C. Burkill and H. Burkill: A Second Course in Mathematical Analysis

Published $1970$, Cambridge University Press

ISBN 0 521 28061 3.

### Contents

Preface
1. SETS AND FUNCTIONS
1.1 Sets and numbers. 1.2. Ordered pairs and Cartesian products. 1.3. Functions. 1.4. Similarity of sets. Notes.
2. METRIC SPACES
2.1. Metrics. 2.2. Norms. 2.3. Open and closed sets. Notes.
3. CONTINUOUS FUNCTIONS ON METRIC SPACES
3.1. Limits. 3.2. Continuous functions. 3.3. Connected metric spaces. 3.4. Complete metric spaces. 3.5. Completion of metric spaces. 3.6. Compact metric spaces. 3.7. The Heine-Borel theorem. Notes.
4. LIMITS IN THE SPACES $\R^1$ AND $\Z$
4.1. The symbols $O$, $o$, $\sim$. 4.2. Upper and lower limits. 4.3. Series of complex terms. 4.4. Series of positive terms. 4.5. Conditionally convergent real series. 4.6. Power series. 4.7. Double and repeated limits. Notes.
5. UNIFORM CONVERGENCE
5.1. Pointwise and uniform convergence. 5.2. Properties assured by uniform convergence. 5.3. Criteria for uniform convergence. 5.4. Further properties of power series. 5.5. Two constructions of continuous functions. 5.6. Weierstrass's approximation theorem and its generalisation. Notes.
6. INTEGRATION
6.1. The Riemann-Stieltjes integral. 6.2. Further properties of the Riemann-Stieltjes integral. 6.3. Improper Riemann-Stieltjes integrals. 6.4. Functions of bounded variation. 6.5. Integrities of bounded variation. 6.6. The Riesz representation theorem. 6.7. The Riemann integral. 6.8. Content. 6.9. Some manipulative theorems. Notes.
7. FUNCTIONS FROM $R^m$ TO $R^n$
7.1. Differentiation. 7.2. Operations on differentiable functions. 7.3. Some properties of differentiable functions. 7.4. The implicit function theorem. 7.5. The inverse function theorem. 7.6. Functional dependence. 7.7. Maxima and minima. 7.8. Second and higher derivatives. Notes.
8. INTEGRALS IN $R^n$
8.1. Curves. 8.2. Line integrals. 8.3. Integration over intervals in $R^n$. 8.4. Integration over arbitrary bounded sets in $R^n$. 8.5. Differentiation and integration. 8.6. Transformation of integrals. 8.7. Functions defined by integrals. Notes.
9. FOURIER SERIES
9.1. Trigonometric series. 9.2. Some special series. 9.3. Theorems of Riemann. Dirichlet's integral. 9.4. Convergence of Fourier series. 9.5. Divergence of Fourier series. 9.6. Cesàro and Abel summability of series. 9.7. Summability of Fourier series. 9.8. Mean square approximation. Parseval's theorem. 9.9. Fourier integrals. Notes.
10. COMPLEX FUNCTION THEORY
10.1. Complex numbers and functions. 10.2. Regular functions. 10.3. Conformal mapping. 10.4. The bilinear mapping. The extended plane. 10.5. Properties of bilinear mappings. 10.6. Exponential and logarithm. Notes.
11. COMPLEX INTEGRALS. CAUCHY'S THEOREM
11.1. Complex integrals. 11.2. Dependence of the integral on the path. 11.3. Primitives and local primitives. 11.4. Cauchy's theorem for a rectangle. 11.5. Cauchy's theorem for circuits in a disc. 11.6. Homotopy. The general Cauchy theorem. 11.7. The index of a circuit for a point. 11.8. Cauchy's integral formula. 11.9. Successive derivatives of a regular function. Notes.
12. EXPANSIONS. SINGULARITIES. RESIDUES
12.1. Taylor's series. Uniqueness of regular functions. 12.2. Inequalities for coefficients. Liouville's theorem. 12.3. Laurent's series. 12.4. Singularities. 12.5. Residues. 12.6. Counting zeros and poles. 12.7. The value $z = \infty$. 12.8. Behaviour near singularities. Notes.
13. GENERAL THEOREMS. ANALYTIC FUNCTIONS
13.1. Regular functions represented by series or integrals. 13.2. Local mappings. 13.3. The Weierstrass approach. Analytic continuation. 13.4. Analytic functions. Notes.
14. APPLICATIONS TO SPECIAL FUNCTIONS
14.1. Evaluation of real integrals by residues. 14.2. Summation of series by residues. 14.3. Partial fractions of $\cot z$. 14.4. Infinite products. 14.5. The factor theorem of Weierstrass. The sine product. 14.6. The gamma function. 14.7. Integrals expressed in gamma functions. 14.8. Asymptotic formulae. Notes.
Solutions of Exercises
References
Index


text:
# Biblioteca

Música » James Blackshaw »

## And I Have Come Upon This Place by Lost Ways

13 execuções | Ir para página da faixa

Faixas (13)
Faixa Álbum Duração Data
And I Have Come Upon This Place by Lost Ways 5:08 Fev 4 2014, 22h17
And I Have Come Upon This Place by Lost Ways 5:08 Fev 18 2013, 22h49
And I Have Come Upon This Place by Lost Ways 5:08 Set 8 2012, 15h26
And I Have Come Upon This Place by Lost Ways 5:08 Jul 6 2012, 14h19
And I Have Come Upon This Place by Lost Ways 5:08 Mai 10 2012, 16h25
And I Have Come Upon This Place by Lost Ways 5:08 Mai 2 2012, 20h58
And I Have Come Upon This Place by Lost Ways 5:08 Abr 30 2012, 18h32
And I Have Come Upon This Place by Lost Ways 5:08 Abr 26 2012, 18h41
And I Have Come Upon This Place by Lost Ways 5:08 Abr 26 2012, 12h38
And I Have Come Upon This Place by Lost Ways 5:08 Abr 26 2012, 12h38
And I Have Come Upon This Place by Lost Ways 5:08 Abr 26 2012, 12h38
And I Have Come Upon This Place by Lost Ways 5:08 Abr 26 2012, 12h32
And I Have Come Upon This Place by Lost Ways 5:08 Abr 25 2012, 19h22


text:
Primo Search

# Flow analysis, linearity, and PTIME

## Van Horn, David ; Mairson, Harry G.

Texto completo disponível

• Título:
Flow analysis, linearity, and PTIME
• Autor: Van Horn, David ; Mairson, Harry G.
• Assuntos: Computer Science - Programming Languages
• Descrição: Flow analysis is a ubiquitous and much-studied component of compiler technology---and its variations abound. Amongst the most well known is Shivers' 0CFA; however, the best known algorithm for 0CFA requires time cubic in the size of the analyzed program and is unlikely to be improved. Consequently, several analyses have been designed to approximate 0CFA by trading precision for faster computation. Henglein's simple closure analysis, for example, forfeits the notion of directionality in flows and enjoys an "almost linear" time algorithm. But in making trade-offs between precision and complexity, what has been given up and what has been gained? Where do these analyses differ and where do they coincide? We identify a core language---the linear $\lambda$-calculus---where 0CFA, simple closure analysis, and many other known approximations or restrictions to 0CFA are rendered identical. Moreover, for this core language, analysis corresponds with (instrumented) evaluation. Because analysis faithfully captures evaluation, and because the linear $\lambda$-calculus is complete for PTIME, we derive PTIME-completeness results for all of these analyses. Comment: Appears in The 15th International Static Analysis Symposium (SAS 2008), Valencia, Spain, July 2008


text:
Given A, b and c, this returns a function that evaluates the quandratic for a vector x.

Where $$\mathbf{A} \in \mathbb{R}^{NxN}$$, $$\mathbf{b} \in \mathbb{R}^N$$ and $$c$$ is a constant, this function evaluates the following quadratic:

$Q( \mathbf{x} ) = \frac{1}{2} \mathbf{x^T A x + b^T x} + c$

for a vector $$\mathbf{x}$$. It also optionally returns the gradient of the above equation, and its Hessian.

Parameters
A(N, N) numpy.ndarray

A square matrix

b(N) numpy.ndarray

A vector

cfloat

A constant

Returns
function :

The callable function that returns the quadratic evaluation, and optionally its gradient, and Hessian.


text:
I understand that the definition of flux linkage as kind of the sum of all the fluxes going through the surfaces bound by all the turns. That is, $$\Lambda = N \Phi$$. However what I don't understand is what happens if the coils are not uniformly stacked up on top of each other like a solenoid. For example, take the example of a sphere with N turns of wire wrapped around it to create some sort of spherical solenoid and run a time varying magnetic field through it. In this case, there should be a voltage induced however I don't understand how to employ the concept of flux linkage to calculate that here because $$\Lambda \neq N \Phi$$ as every loop of wire links a different amount of flux to the current. If anybody could help me understand how to use linkage here to solve for induced voltage or self inductance that would be great.
• $N \Phi$ is a simplification of flux linkage to the case where all the wire loops (fictitious or otherwise) have the same shape and the same magnetic field penetrating that shape. If you don't have that case, you have to sum the flux linkage from each loop or integrate depending on the limit you are faced with. – Finncent Price Aug 8 at 8:36
• I think you want to compute the area of each coil using something like: A = $\pi R^2 sin^2 \theta$ for each loop and then integrate that over the whole sphere. I assume the magnitude of B is the same for all the loops. – Finncent Price Aug 10 at 11:52