Generalization of the PC algorithm for non-linear and non-Gaussian data and its application to biological data

This thesis arises in the context of finding causal relationships among observed data. It will mostly focus on data coming from biological measurement of protein or gene expression. The PC is a widely used algorithm for learning graphical models. The causal structures are created evaluating the dependency or conditional dependency among the variables. Its output is either a DAG or a class of DAGs. It has been developed for linear data with Gaussian noise, which makes it less suitable when applied to biological data, which are often far from having these features. In this thesis we develop methods (i) to solve the problem of linearity/Gaussianity and (ii) to restrict the possible outputs of the algorithm. In order to overcome the problem (i), we use conditional dependency tests which characterize probabilistic independence: we use quantities which are zero if and only if the data are independent and not only uncorrelated. Two families of test are investigated: a non-parametric kernel based test of conditional independence (kPC) and a test based on the Brownian distance correlation (bPC). In the kPC, thanks to the kernel, the data are implicitly embedded in a space where the data are more linear. In the bPC the Brownian correlation measures the weighted distance between f_{X,Y} and f_{X}f_{Y}. In order to solve problem (ii), we describe the data with a weakly additive noise model and we use the residuals of the non-linear regression to find more causal directions than with the PC algorithm. The developed algorithms are tested on data on the data used in Sachs et al. (2005).

Questa tesi si colloca nell'ambito di sviluppare algoritmi per la ricerca di relazioni di causalità tra dati osservabili. Più precisamente, saranno presi in considerazione dati quali espressione proteica o genomica. L'algoritmo PC è un metodo tra i più usati per ricavare relazioni di dipendenza e rappresentarle tramite grafi. Le connessioni tra i nodi presenti nei grafi sorgono valutando relazioni di dipendenza o dipendenza condizionata tra variabili. L'output dell' algoritmo può essere sia una classe di DAG, che un certo DAG. Quest' algoritmo è stato sviluppato per dati che hanno come caratteristica l'essere lineari e avere rumore gaussiano; queste proprietà sono però difficili da trovare in dati provenienti dalla biologia. In questa tesi sviluppiamo metodi (i) per risolvere il problema della linearità/gaussianità e (ii) per restringere il possibile output di PC. Per risolvere il problema (i) usiamo test che caratterizzano l'indipendenza probabilistica in tutti i sensi: cerchiamo quantità che siano zero se e solo se le variabili sono indipendenti. Vagliamo due diverse famiglie di test: un test non parametrico basato sui kernel (kPC) ed un altro che considera la distanza browniana (bPC). In kPC, grazie al kernel, i dati vengono analizzati in un nuovo spazio, nel quale le relazioni sono più lineari ed è quindi più semplice trovare dipendenze. In bPC, la correlazione Browniana misura la distanza pesata tra f_{X,Y} e f_{X}f_{Y}. Per risolvere il problema (ii), i dati vengono descritti con un weakly additive noise model e i residui di una regressione (non-lineare) sono usati per trovare il maggior numero possibile di direzioni di causalità. Infine, per essere confrontati, gli algoritmi sviluppati sono testati su dati usati in Sachs et al. (2005).