Identifying tumor clones with noisy itemset mining

Sequencing the genome of single cells allows for a better understanding of cellular populations, and provides interesting insights over the composition and phylogeny of tumor samples. Unfortunately, single-cell sequencing technologies present some challenges; in particular, they often suffer from high sparsity and low signal-to-noise ratio of their output. This problem is particularly pronounced when single-nucleotide variations (SNVs) are considered, due to the high probability of false negatives. In this work we propose a novel approach based on noisy itemset mining that allows the recovery of the clonal composition of a tumor from SNV single-cell data. An extensive theoretical foundation is presented to justify the chosen framework, and to highlight the relationship between noisy itemsets and clones with their mutations. This allows the development of a proper score, which in expectation is provably capable of distinguishing between correct clones and random groups of cells. Such score is then improved thanks to theoretical and practical considerations, and serves as basis for three different algorithms. A comprehensive experimental section completes this work, where the efficiency, the scalability and the accuracy of the proposed techniques are evaluated on synthetic datasets and compared with a state-of-the-art algorithm. In the end, some tests are performed on synthetic data generated using realistic parameters derived from actual sequencing data; in such conditions, the proposed approach proved to outperform the state-of-the-art.

Il sequenziamento del genoma di singole cellule permette una migliore comprensione delle popolazioni di cellule, e fornisce informazioni interessanti sulla composizione e la filogenesi di campioni tumorali. Purtroppo, le tecnologie di sequenziamento a singola cellula presentano alcune sfide; in particolare, spesso i risultati sono affetti da un’elevata sparsità e da un basso rapporto segnale-rumore. Questo problema è particolarmente pronunciato quando vengono considerate le varianti a singolo nucleotide (SNV), a causa dell’alta probabilità di registrare falsi negativi. In questo lavoro proponiamo un nuovo approccio basato sul noisy itemset mining che permette la ricostruzione della composizione clonale di un tumore a partire da sequenze di SNV da singole cellule. Presenteremo un’ampia fondazione teorica per giustificare il framework scelto, nonché per evidenziare la relazione tra noisy itemset e cloni. Ciò permette lo sviluppo di un’adeguata funzione obiettivo, la quale dimostrabilmente permette di distinguere in aspettazione tra cloni corretti e gruppi casuali di cellule. Tale funzione è poi migliorata grazie a considerazioni teoriche e pratiche, e serve da base per la definizione di tre differenti algoritmi. Un’estesa sezione sperimentale completa il lavoro; qui l’efficienza, la scalabilità e l’accuratezza delle tecniche proposte sono valutate su dati sintetici, e confrontate con un algoritmo allo stato dell’arte. Per concludere, effettueremo alcune prove su dati sintetici generati a partire da parametri realistici derivati da effettivi dati di sequenziamento; in queste condizioni, gli algoritmi proposti hanno dimostrato di superare lo stato dell’arte.