library(BiocStyle)
library(knitr)
library(ComplexHeatmap)

Introduction {#introduction}

NMF (nonnegative matrix factorization) is a matrix decomposition method. A description of the algorithm and it's implementation can be found e.g. in [@Lee_article1999]. In 2003, Brunet et al. applied NMF to gene expression data [@Brunet_article2003]. In 2010, r CRANpkg("NMF"), an R package implementing several NMF solvers was published [@Gaujoux_article2010]. NMF basically solves the problem as illustrated in the following figure (Image taken from https://en.wikipedia.org/wiki/Non-negative_matrix_factorization):

NMF

Here, $V$ is an input matrix with dimensions $n \times m$. It is decomposed into two matrices $W$ of dimension $n \times l$ and $H$ of dimension $l \times m$, which when multiplied approximate the original matrix $V$. $l$ is a free parameter in NMF, it is called the factorization rank. If we call the columns of $W$ \emph{signatures}, then $l$ corresponds to the number of signatures. The decomposition thus leads to a reduction in complexity if $l < n$, i.e. if the number of signatures is smaller than the number of features, as indicated in the above figure.

In 2015, Mejia-Roa et al. introduced an implementation of an NMF-solver in CUDA, which lead to significant reduction of computation times by making use of massive parallelisation on GPUs [@Mejia_article2015]. Other implementations of NMF-solvers on GPUs exist.

It is the pupose of the package Bratwurst described here to provide wrapper functions in R to these NMF-solvers in CUDA. Massive parallelisation not only leads to faster algorithms, but also makes the benefits of NMF accessible to much bigger matrices. Furthermore, functions for preprocessing, estimation of the optimal factorization rank and post-hoc feature selection are provided.

The Bratwurst package {#Bratwurst_package}

The main feature of the package Bratwurst is an S4 object called nmf.exp. It is derived from SummarizedExperiment, has containers for a data matrix, column annotation data and row annotation data and inherits SummarizedExperiment's accessor functions colData and rowData. The matrix to be stored in this data structure is the matrix $V$ as described above, corresponding to the input matrix for the NMF-solver. nmf.exp furthermore has containers for the matrices $W$ and $H$ which are results of the decomposition. As NMF algorithms have to be run iteratively, an instance of the class nmf.exp can store large lists of matrices, corresponding to the results of different iteration steps. Accessor functions to all different containers are provided.

A crucial step in data analysis with NMF is the determination of the optimal factorization rank, i.e. the number of columns of the matrix $W$ or equivalently the number of rows of the matrix $H$. No consensus method for an automatic evaluation of the optimal factorization rank has been found to date. Instead, the decomposition is usually performed iteratively over a range of possible factorization ranks and different quality measures are computed for every tested factorization ranks. Many quality measures have been proposed:

The package Bratwurst provides functions to compute all

Example: leukemia data

Preparations

library(Bratwurst)
library(NMF)

Load the example data

data(leukemia)
samples <- "leukemia"

This data was initially generated by the following commands:

data.path  <- file.path(getwd(), "data")
matrix.file <- list.files(data.path, "*data.txt", full.names = T)
rowAnno.file <- list.files(data.path, "micro.*anno.*txt", full.names = T)
rowAnno.bed <- list.files(data.path, ".bed", full.names = T)
colAnno.file <- list.files(data.path, "sample.*anno.*txt", full.names = T)
# Read files to summarizedExperiment
leukemia.nmf.exp <- nmfExperimentFromFile(matrix.file = matrix.file,
                                          rowAnno.file = rowAnno.file,
                                          colData.file = colAnno.file)
save(leukemia.nmf.exp, file = file.path(data.path, "leukemia.rda"))

Now we are ready to start an NMF analysis.

NMF analysis

Call wrapper function

The wrapper function for the NMF solvers in the Bratwurst package is runNmfGpu. It is called as follows:

k.max <- 4
outer.iter <- 10
inner.iter <- 10^4

# leukemia.nmf.exp<- runNmfGpu(nmf.exp = leukemia.nmf.exp,
#                              k.max = k.max,
#                              outer.iter = outer.iter,
#                              inner.iter = inner.iter,
#                              tmp.path = "/tmp/tmp_leukemia")
leukemia.nmf.exp<- runNmfGpuPyCuda(nmf.exp = leukemia.nmf.exp,
                                   k.max = k.max,
                                   outer.iter = outer.iter,
                                   inner.iter = inner.iter,
                                   tmp.path = "/tmp/tmp_leukemia",
                                   cpu = TRUE)
# leukemia.nmf.exp<- runNmfGpuPyCuda(nmf.exp = leukemia.nmf.exp,
#                                    k.max = k.max,
#                                    outer.iter = outer.iter,
#                                    inner.iter = inner.iter,
#                                    tmp.path = "/tmp/tmp_leukemia",
#                                    cpu = TRUE)
# leukemia.nmf.exp<- runNmfGpuPyCuda(nmf.exp = leukemia.nmf.exp,
#                                    k.max = k.max,
#                                    outer.iter = outer.iter,
#                                    inner.iter = inner.iter,
#                                    tmp.path = "/tmp/tmp_leukemia",
#                                    binary.file.transfer = TRUE)

Depending on the choice of parameters (dimensions of the input matrix, number of iterations), this step may take some time. Note that the algorithm updates the user about the progress in the iterations.

Several getter functions are available to access the data in the updated nmf.exp object:

HMatrixList

Returns a list of matrices H for a specific factorization rank k. There are as many entries in this list as there were iterations in the outer iteration. Of course the number of rows of the matrix H corresponds to the chosen factorization rank.

tmp.object <- HMatrixList(leukemia.nmf.exp, k = 2)
class(tmp.object)
length(tmp.object)
class(tmp.object[[1]])
dim(tmp.object[[1]])
kable(tmp.object[[1]][, c(1:5)])

If no value for k is supplied, the function returns a list of lists, one for every iterated factorization rank.

tmp.object <- HMatrixList(leukemia.nmf.exp)
class(tmp.object)
length(tmp.object)
class(tmp.object[[1]])
length(tmp.object[[1]])

HMatrix

Returns the matrix H for the optimal decomposition (i.e. the one with the minimal residual) for a specific factorization rank k. As in the previous paragraph, the number of rows of the matrix H corresponds to the chosen factorization rank.

tmp.object <- HMatrix(leukemia.nmf.exp, k = 2)
class(tmp.object)
dim(tmp.object)
kable(tmp.object[, c(1:5)])

If no value for k is supplied, the function returns a list of optimal matrices, one for every iterated factorization rank.

H.list <- HMatrix(leukemia.nmf.exp)
class(H.list)
length(H.list)
kable(H.list[[1]][, c(1:5)])

WMatrixList

Returns a list of matrices W for a specific factorization rank k. There are as many entries in this list as there were iterations in the outer iteration. Of course the number of columns of the matrix W corresponds to the chosen factorization rank.

tmp.object <- WMatrixList(leukemia.nmf.exp, k = 2)
class(tmp.object)
length(tmp.object)
class(tmp.object[[1]])
dim(tmp.object[[1]])
kable(as.data.frame(tmp.object[[1]][c(1:5), ]))

If no value for k is supplied, the function returns a list of lists, one for every iterated factorization rank.

WMatrix

Returns the matrix W for the optimal decomposition (i.e. the one with the minimal residual) for a specific factorization rank k. As in the previous paragraph, the number of columns of the matrix W corresponds to the chosen factorization rank.

tmp.object <- WMatrix(leukemia.nmf.exp, k = 2)
class(tmp.object)
dim(tmp.object)
kable(as.data.frame(tmp.object[c(1:5), ]))

If no value for k is supplied, the function returns a list of optimal matrices, one for every iterated factorization rank.

W.list <- WMatrix(leukemia.nmf.exp)
class(W.list)
length(W.list)
kable(as.data.frame(W.list[[1]][c(1:5), ]))

FrobError

Returns a data frame with as many columns as there are iterated factorization ranks and as many rows as there are iterations per factorization rank.

kable(FrobError(leukemia.nmf.exp))

Determine the optimal factorization rank

In NMF, Several methods have been described to assess the optimal factorization rank. The Bratwurst packages implements some of them. They are computed by applying custom functions which subsequently update the data structure of type nmf.exp.

Get Frobenius error.

The most important information about the many iterated decompositions is the norm of the residual. In NMF this is often called the Frobenius error, as the Frobenius norm may be used.

leukemia.nmf.exp <- computeFrobErrorStats(leukemia.nmf.exp)

Generate Alexandrov Criterion plot

In [@Alex2013] an approach is described in which a modified silhouette criterion is used to estimate the stability across iteration steps for one fixed factorization rank k.

leukemia.nmf.exp <- computeSilhoutteWidth(leukemia.nmf.exp)

Cophenetic correlation coefficient plot

leukemia.nmf.exp <- computeCopheneticCoeff(leukemia.nmf.exp)

Compute amari type distance

leukemia.nmf.exp <- computeAmariDistances(leukemia.nmf.exp)

After having executed all these functions, the values of the computed measures can be accessed with OptKStats:

kable(OptKStats(leukemia.nmf.exp))

These quality measures can be displayed together:

Generate plots to estimate optimal k

gg.optK <- plotKStats(leukemia.nmf.exp)
gg.optK

Generate ranked error plot.

It may also be useful to inspect the Frobenius error after ranking. This may give an estimation of the convergence in the parameter space of initial conditions.

gg.rankedFrobError <- plotRankedFrobErrors(leukemia.nmf.exp)
gg.rankedFrobError

Visualize the matrix H (exposures)

The matrices H may be visualized as heatmaps. We can define a meta information object and annotate meta data:

entity.colVector <- c("red", "blue")
names(entity.colVector) <- c("ALL", "AML")
subtype.colVector <- c("orange", "darkgreen", "blue")
names(subtype.colVector) <- c("B-cell", "T-cell", "-")
anno_col <- list(V2 = entity.colVector,
                 V3 = subtype.colVector)
heat.anno <- HeatmapAnnotation(df = colData(leukemia.nmf.exp)[, c(2:3)],
                               col = anno_col)

And now display the matrices H with meta data annotation:

# sapply(1:length(HMatrix(leukemia.nmf.exp)), function(i) {
#   current_k <- as.numeric(names(HMatrix(leukemia.nmf.exp))[i])
#   h.heatmap <- Heatmap(HMatrix(leukemia.nmf.exp, k = current_k),
#                        clustering_distance_columns = "pearson",
#                        heatmap_legend_param = list(color_bar = "continuous"),
#                        show_column_names = F, cluster_rows = F,
#                        top_annotation = heat.anno)
#   draw(h.heatmap)
# })

Bratwurst provides a plotting function to display the matrices H with meta data annotation:

# Plot Heatmaps for H over all k
lapply(seq(2, k.max), function(k) {
  plotHMatrix(leukemia.nmf.exp, k)
})

Feature selection

Row K-means to determine signature specific features

### Find representative regions.
# Get W for best K
leukemia.nmf.exp <- setOptK(leukemia.nmf.exp, 4)
OptK(leukemia.nmf.exp)

signature.names <- getSignatureNames(leukemia.nmf.exp, OptK(leukemia.nmf.exp))
signature.names

FeatureStats(leukemia.nmf.exp)

leukemia.nmf.exp <- computeFeatureStats(leukemia.nmf.exp)
FeatureStats(leukemia.nmf.exp)

# You might want to add additional selection features
# such as entropy or absolute delta 
# Entropy
leukemia.nmf.exp <- computeEntropy4OptK(leukemia.nmf.exp)
FeatureStats(leukemia.nmf.exp)

leukemia.nmf.exp <- computeAbsDelta4OptK(leukemia.nmf.exp)
FeatureStats(leukemia.nmf.exp)

Feature visualization

# Plot all possible signature combinations
plotSignatureFeatures(leukemia.nmf.exp)

# Plot only signature combinations
plotSignatureFeatures(leukemia.nmf.exp, sig.combs = F)

# Try to display selected features on W matrix
sig.id <- "1000"
m <- WMatrix(leukemia.nmf.exp, k = OptK(leukemia.nmf.exp))[
  FeatureStats(leukemia.nmf.exp)[, 1] == sig.id, ]
m <- m[order(m[, 1]), ]
c <- getColorMap(m)
#m <- t(apply(m, 1, function(r) (r - mean(r))/sd(r)))

Heatmap(m, col = c, cluster_rows = F, cluster_columns = F)

References



wurst-theke/bratwurst documentation built on May 17, 2019, 9:14 a.m.