Significant Patterns for Survival Analysis with Permutation Testing

This thesis addresses the critical challenge of identifying statistically robust combinatorial biomarkers from high-dimensional genomic data in survival analysis. Standard approaches often struggle with the computational complexity of an exponential search space and, more critically, rely on flawed asymptotic approximations of the log-rank test. This can lead to inaccurate p-values and an inflated rate of false discoveries, especially in the presence of imbalanced patient groups common in genomics. To overcome these limitations, we propose a novel algorithm, SurvivalWY. The method leverages the Westfall-Young permutation testing procedure to construct an empirical null distribution for the log-rank statistic, thereby bypassing unreliable asymptotic assumptions and ensuring accurate significance assessment regardless of group imbalance. To tackle the computational burden, SurvivalWY integrates a Branch and Bound pruning strategy, enabled by a formally derived upper bound on the log-rank test statistic, which allows for the efficient exploration of the vast search space. Experimental evaluation first demonstrates that a state-of-the-art method, SurvivalLAMP, fails to rigorously control the Family-Wise Error Rate (FWER) under a permutational distribution. In contrast, our proposed framework is proven to be statistically rigorous, correctly identifying significant patterns while maintaining strict FWER control. This work establishes a complete and formally correct framework for significant pattern mining in survival analysis, offering a robust alternative to existing methods.

Questa tesi affronta la sfida critica di identificare combinazioni di biomarcatori statisticamente robusti a partire da dati genomici ad alta dimensionalità nell'ambito dell'analisi di sopravvivenza. Gli approcci standard sono spesso limitati dalla complessità computazionale derivante da uno spazio di ricerca esponenziale e, aspetto ancora più critico, si basano su approssimazioni asintotiche problematiche del log-rank test. Ciò può condurre a \textit{p}-value inaccurati e a un'inflazione del tasso di false scoperte (false discovery rate), specialmente in presenza di gruppi di pazienti sbilanciati, una condizione comune in genomica. Per superare queste limitazioni, viene proposto un nuovo algoritmo, SurvivalWY. Il metodo sfrutta il framework di test di permutazione di Westfall-Young per costruire una distribuzione nulla empirica per la statistica del test log-rank, evitando così la necessità di ricorrere ad assunzioni asintotiche inaffidabili e garantendo una valutazione della significatività accurata, indipendentemente dallo sbilanciamento dei gruppi. Per risolvere il problema della complessità computazionale, SurvivalWY integra una strategia di potatura Branch and Bound, resa possibile dalla derivazione formale di un limite superiore per la statistica del test, che permette di esplorare in modo efficiente l'ampio spazio di ricerca. La valutazione sperimentale dimostra in primo luogo che un metodo dello stato dell'arte, SurvivalLAMP, non controlla in modo rigoroso il Family-Wise Error Rate (FWER) in un contesto permutazionale. Al contrario, il nostro framework si dimostra statisticamente rigoroso, identificando correttamente i pattern significativi e mantenendo un controllo stretto del FWER. Questo lavoro definisce un framework completo e formalmente corretto per la ricerca di pattern significativi nell'analisi di sopravvivenza, offrendo un'alternativa robusta ai metodi esistenti.