For $d\ge2$ and iid $d$-dimensional observations $X^{(1)},X^{(2)},\dots$ with independent Exponential$(1)$ coordinates, we revisit the study by Fill and Naiman (Electron. J. Probab., 2020) of the boundary (relative to the closed positive orthant), or "frontier", $F_n$ of the closed Pareto record-setting (RS) region \[ \mbox{RS}_n:=\{0\le x\in{\mathbb R}^d:x\not\prec X^{(i)}\mbox{\ for all $1\le i\le n$}\} \] at time $n$, where $0\le x$ means that $0\le x_j$ for $1\le j\le d$ and $x\prec y$ means that $x_j0$ and $c_n\to\infty$ we have \[ {\mathbb P}(F_n^- -\ln n\in (-(2+\varepsilon)\ln\ln\ln n,c_n))\to 1 \] (describing typical behavior) and almost surely \[ \limsup \frac{F_n^- - \ln n}{\ln \ln n} \le 0 \quad \mbox{and} \quad \liminf \frac{F_n^- - \ln n}{\ln \ln \ln n} \in [-2, -1]. \] In this paper we use the theory of generators (minima of $F_n$) together with the first- and second-moment methods to improve considerably the trailing-point location results to \[ F_n^- - (\ln n - \ln \ln \ln n) \overset{\mathrm{P}}{\longrightarrow} - \ln(d - 1) \] (describing typical behavior) and, for $d \ge 3$, almost surely \begin{align*} &\limsup [F_n^- - (\ln n - \ln \ln \ln n)] \leq -\ln(d - 2) + \ln 2 \\ \mbox{and }&\liminf [F_n^- - (\ln n - \ln \ln \ln n)] \ge - \ln d - \ln 2. \end{align*}

Recent methods for learning a linear subspace from data corrupted by outliers are based on convex L1 and nuclear norm optimization and require the dimension of the subspace and the number of outliers to be sufficiently small [27]. In sharp contrast, the recently proposed Dual Principal Component Pursuit (DPCP) method [22] can provably handle subspaces of high dimension by solving a non-convex L1 optimization problem on the sphere. However, its geometric analysis is based on quantities that are difficult to interpret and are not amenable to statistical analysis. In this paper we provide a refined geometric analysis and a new statistical analysis that show that DPCP can tolerate as many outliers as the square of the number of inliers, thus improving upon other provably correct robust PCA methods. We also propose a scalable Projected Sub-Gradient Descent method (DPCP-PSGD) for solving the DPCP problem and show it admits linear convergence even though the underlying optimization problem is non-convex and non-smooth. Experiments on road plane detection from 3D point cloud data demonstrate that DPCP-PSGD can be more efficient than the traditional RANSAC algorithm, which is one of the most popular methods for such computer vision applications.

Recent improvements in next-generation sequencing of tumor samples and the ability to identify somatic mutations at low allelic fractions have opened the way for new approaches to model the evolution of individual cancers. The power and utility of these models is increased when tumor samples from multiple sites are sequenced. Temporal ordering of the samples may provide insight into the etiology of both primary and metastatic lesions and rationalizations for tumor recurrence and therapeutic failures. Additional insights may be provided by temporal ordering of evolving subclones--cellular subpopulations with unique mutational profiles. Current methods for subclone hierarchy inference tightly couple the problem of temporal ordering with that of estimating the fraction of cancer cells harboring each mutation. We present a new framework that includes a rigorous statistical hypothesis test and a collection of tools that make it possible to decouple these problems, which we believe will enable substantial progress in the field of subclone hierarchy inference. The methods presented here can be flexibly combined with methods developed by others addressing either of these problems. We provide tools to interpret hypothesis test results, which inform phylogenetic tree construction, and we introduce the first genetic algorithm designed for this purpose. The utility of our framework is systematically demonstrated in simulations. For most tested combinations of tumor purity, sequencing coverage, and tree complexity, good power (≥ 0.8) can be achieved and Type 1 error is well controlled when at least three tumor samples are available from a patient. Using data from three published multi-region tumor sequencing studies of (murine) small cell lung cancer, acute myeloid leukemia, and chronic lymphocytic leukemia, in which the authors reconstructed subclonal phylogenetic trees by manual expert curation, we show how different configurations of our tools can identify either a single tree in agreement with the authors, or a small set of trees, which include the authors' preferred tree. Our results have implications for improved modeling of tumor evolution and the importance of multi-region tumor sequencing.

BACKGROUND: A major challenge in computational biology is to extract knowledge about the genetic nature of disease from high-throughput data. However, an important obstacle to both biological understanding and clinical applications is the "black box" nature of the decision rules provided by most machine learning approaches, which usually involve many genes combined in a highly complex fashion. Achieving biologically relevant results argues for a different strategy. A promising alternative is to base prediction entirely upon the relative expression ordering of a small number of genes. RESULTS: We present a three-gene version of "relative expression analysis" (RXA), a rigorous and systematic comparison with earlier approaches in a variety of cancer studies, a clinically relevant application to predicting germline BRCA1 mutations in breast cancer and a cross-study validation for predicting ER status. In the BRCA1 study, RXA yields high accuracy with a simple decision rule: in tumors carrying mutations, the expression of a "reference gene" falls between the expression of two differentially expressed genes, PPP1CB and RNF14. An analysis of the protein-protein interactions among the triplet of genes and BRCA1 suggests that the classifier has a biological foundation. CONCLUSION: RXA has the potential to identify genomic "marker interactions" with plausible biological interpretation and direct clinical applicability. It provides a general framework for understanding the roles of the genes involved in decision rules, as illustrated for the difficult and clinically relevant problem of identifying BRCA1 mutation carriers.

We describe our contribution to the ICMLA2008 “Automated Micro-Array Classification Challenge”. The design of our classifier is motivated by the special scenario encountered in molecular cancer classification based on the mRNA concentrations provided by gene microarray data. Our classifier is rank-based; it only depends on expression comparisons among selected pairs of genes. Such comparisons are invariant to most of the transformations involved in preprocessing and normalization. Every pair of genes determines a binary classifier - choose the class for which the observed ordering is most likely. Pairs are scored by maximizing accuracy. In our k-TSP (k-disjoint Top Scoring Pairs) classifier, k disjoint pairs of genes are learned from training data; the discriminant function is simply the difference in the number of votes for the two classes. This rule involves exactly 2k genes, is readily interpretable, and provides some state-of-the-art results in cancer diagnosis and prognosis for small values of k, even k=1.

MOTIVATION: In proteomics, reverse database searching is used to control the false match frequency for tandem mass spectrum/peptide sequence matches, but reversal creates sequences devoid of patterns that usually challenge database-search software. RESULTS: We designed an unsupervised pattern recognition algorithm for detecting patterns with various lengths from large sequence datasets. The patterns found in a protein sequence database were used to create decoy databases using a Monte Carlo sampling algorithm. Searching these decoy databases led to the prediction of false positive rates for spectrum/peptide sequence matches. We show examples where this method, independent of instrumentation, database-search software and samples, provides better estimation of false positive identification rates than a prevailing reverse database searching method. The pattern detection algorithm can also be used to analyze sequences for other purposes in biology or cryptology. AVAILABILITY: On request from the authors. SUPPLEMENTARY INFORMATION: http://bioinformatics.psb.ugent.be/.

MOTIVATION: Various studies have shown that cancer tissue samples can be successfully detected and classified by their gene expression patterns using machine learning approaches. One of the challenges in applying these techniques for classifying gene expression data is to extract accurate, readily interpretable rules providing biological insight as to how classification is performed. Current methods generate classifiers that are accurate but difficult to interpret. This is the trade-off between credibility and comprehensibility of the classifiers. Here, we introduce a new classifier in order to address these problems. It is referred to as k-TSP (k-Top Scoring Pairs) and is based on the concept of 'relative expression reversals'. This method generates simple and accurate decision rules that only involve a small number of gene-to-gene expression comparisons, thereby facilitating follow-up studies. RESULTS: In this study, we have compared our approach to other machine learning techniques for class prediction in 19 binary and multi-class gene expression datasets involving human cancers. The k-TSP classifier performs as efficiently as Prediction Analysis of Microarray and support vector machine, and outperforms other learning methods (decision trees, k-nearest neighbour and naïve Bayes). Our approach is easy to interpret as the classifier involves only a small number of informative genes. For these reasons, we consider the k-TSP method to be a useful tool for cancer classification from microarray gene expression data. AVAILABILITY: The software and datasets are available at http://www.ccbm.jhu.edu CONTACT: [email protected].

MOTIVATION: DNA microarray data analysis has been used previously to identify marker genes which discriminate cancer from normal samples. However, due to the limited sample size of each study, there are few common markers among different studies of the same cancer. With the rapid accumulation of microarray data, it is of great interest to integrate inter-study microarray data to increase sample size, which could lead to the discovery of more reliable markers. RESULTS: We present a novel, simple method of integrating different microarray datasets to identify marker genes and apply the method to prostate cancer datasets. In this study, by applying a new statistical method, referred to as the top-scoring pair (TSP) classifier, we have identified a pair of robust marker genes (HPN and STAT6) by integrating microarray datasets from three different prostate cancer studies. Cross-platform validation shows that the TSP classifier built from the marker gene pair, which simply compares relative expression values, achieves high accuracy, sensitivity and specificity on independent datasets generated using various array platforms. Our findings suggest a new model for the discovery of marker genes from accumulated microarray data and demonstrate how the great wealth of microarray data can be exploited to increase the power of statistical analysis. CONTACT: [email protected].

There is a close mathematical relationship between integer grids of a particular echelon form and coherent systems in reliability in the case of states coded as integer grid points. This paper shows that such an integer representation is the link between abstract tube theory, which gives improved inclusion-exclusion bounds, and an algebraic method, Grobner bases, based on the polynomial ideal of the failure event.

The growth function for a class of subsets C of a set X is defined by mC(N)max{Δc(F): F⫅X, |F| =N}, N=1,2,…, whereΔc(F)|{F∩C: CϵC}| the number of possible sets obtained by intersecting an element of C with the set F. Sauer (1972) showed that if C forms a Vapnik-Chervonenkis class with dimension V(C), then mc(N)⩽∑j=0V(C)−1Njfor N⩾ V(C) −1. The collection C of Euclidean balls in Rd has been shown by Dudley (1979) to have VC dimension equal to d + 2. It is well known, by using a standard geometric transformation, that Sauer's bound gives the exact number of subsets in this case. We give a more direct construction of the subsets picked out by balls, and as a corollary we obtain the number of such subsets.