MSI Weekly Bulletin - Week starting Monday 27 August, 2007

Hall's marriage theorem (1935, but essentially proved as early as 1912 by Frobenius) says that if in a society of men and women every k men know together at least k women, then there exists a monogamous marriage of all men, in which every man marries a woman he knows. It turns out that a topological approach (and proof) to the theorem yield generalizations that are so far beyond the reach of direct combinatorial methods.

We discuss the problem of measuring the stability of a ranked feature list in functional genomics. Stability (measure of robustness to data perturbations) has only recently arisen as a major issue when applied to feature selection and ranking processes. In fact, selecting a reliable set of biomarkers is as important as achieving predictive classification and the two goals cannot always be pursued together. The resampling-like procedures suggested for high-throughput data are typically structured in a scheme of replicated experiments designed to reduce variance and avoid selection bias: such schemes are quite straightforwardly used for error assessment and model selection. The first task we address consists in providing a measure of similarity among the output lists. This measure reflects indeed the stability of the ranking process (and of the data themselves) by gauging the discriminating features independently from the sample data. A noteworthy role is played also by the characteristics of genome-wide data. With microarrays, a large number of spots are typically not relevant for the classification problem, while many others are highly correlated or possibly clones. Furthermore, some genes can be grouped together in functionally related modules. The stability methods we present in this paper are designed to include such situations. As the top positions in the lists are the most informative, similarity among partial sublists (called top-$k$ lists) will be considered. We base our proposal on the algebraic theory of symmetric groups, coupled with the adoption of the Canberra distance as a disarray measure. Consistency on synthetic data is first assessed; the stability indicators are then used to evaluate different profiling methods or data quality, also comparing with simpler statistical indicators.