Assessing the statistical validity of proteomics based biomarkers

A strategy is presented for the statistical validation of discrimination models in proteomics studies. Several existing tools are combined to form a solid statistical basis for biomarker discovery that should precede a biochemical validation of any biomarker. These tools consist of permutation tests, single and double cross-validation. The cross-validation steps can simply be combined with a new variable selection method, called rank products. The strategy is especially suited for the low-samples-to-variables-ratio (undersampling) case, as is often encountered in proteomics and metabolomics studies. As a classification method, principal component discriminant analysis is used; however, the methodology can be used with any classifier. A dataset containing serum samples from Gaucher patients and healthy controls serves as a test case. Double cross-validation shows that the sensitivity of the model is 89% and the specificity 90%. Potential putative biomarkers are identified using the novel variable selection method. Results from permutation tests support the choice of double cross-validation as the tool for determining error rates when the modelling procedure involves a tuneable parameter. This shows that even cross-validation does not guarantee unbiased results. The validation of discrimination models with a combination of permutation tests and double cross-validation helps to avoid erroneous results which may result from the undersampling.     

Chained permutations and alternating sign matrices—Inspired by three-person chess

We define and enumerate two new two-parameter permutation families, namely, placements of a maximum number of non-attacking rooks on $k$ chained-together $n\times n$ chessboards, in either a circular or linear configuration. The linear case with $k=1$ corresponds to standard permutations of $n$, and the circular case with $n=4$ and $k=6$ corresponds to a three-person chessboard. We give bijections of these rook placements to matrix form, one-line notation, and matchings on certain graphs. Finally, we define chained linear and circular alternating sign matrices, enumerate them for certain values of $n$ and $k$, and give bijections to analogues of monotone triangles, square ice configurations, and fully-packed loop configurations.     

Permutation trinomials over F2m

Permutation polynomials are an interesting subject of mathematics and have applications in other areas of mathematics and engineering. In this paper, we determine all permutation trinomials over ${\mathbb{F}}_{2^m}$ in Zieve's paper [30]. We prove a conjecture proposed by Gupta and Sharma in [8] and obtain some new permutation trinomials over ${\mathbb{F}}_{2^m}$. Finally, we show that some classes of permutation trinomials with parameters are QM equivalent to some known permutation trinomials.     

Polytopes of high rank for the symmetric groups

In the Atlas of abstract regular polytopes for small almost simple groups by Leemans and Vauthier, the polytopes whose automorphism group is a symmetric group Sn of degree 5?n?9 are available. Two observations arise when we look at the results: (1) for n?5, the (n−1)-simplex is, up to isomorphism, the unique regular (n−1)-polytope having Sn as automorphism group and, (2) for n?7, there exists, up to isomorphism and duality, a unique regular (n−2)-polytope whose automorphism group is Sn. We prove that (1) is true for n≠4 and (2) is true for n?7. Finally, we also prove that Sn acts regularly on at least one abstract polytope of rank r for every 3?r?n−1.     

The group marriage problem

Let G be a permutation group acting on [n]={1,…,n} and V={Vi:i=1,…,n} be a system of n subsets of [n]. When is there an element g∈G so that g(i)∈Vi for each i∈[n]? If such a g exists, we say that G has a G-marriage subject to V. An obvious necessary condition is the orbit condition: for any nonempty subset Y of [n], there is an element g∈G such that the image of Y under g is contained in _?y∈YVy. Keevash observed that the orbit condition is sufficient when G is the symmetric group Sn; this is in fact equivalent to the celebrated Hall's Marriage Theorem. We prove that the orbit condition is sufficient if and only if G is a direct product of symmetric groups. We extend the notion of orbit condition to that of k-orbit condition and prove that if G is the cyclic group Cn where n?4 or G acts 2-transitively on [n], then G satisfies the (n−1)-orbit condition subject to V if and only if G has a G-marriage subject to V.     

Constructing permutations of finite fields via linear translators

Methods for constructing large families of permutation polynomials of finite fields are introduced. For some of these permutations the cycle structure and the inverse mapping are determined. The results are applied to lift minimal blocking sets of PG(2,q) to those of PG(2,qn).     

Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].