Bag of Words approaches for Bioinformatics

Molti problemi di Pattern Recognition statistica sono stati affrontati nella letteratura recente attraverso la rappresentazione "bag of words", una rappresentazione particolarmente appropriata quando negli oggetti del problema si riescono ad individuare dei semplici elementi "costituenti". Mediante la rappresentazione bag of words, gli oggetti vengono caratterizzati da un vettore in cui ogni elemento conta il numero di occorrenze dei costituenti nell'oggetto. Nonostante il grande successo ottenuto in diversi campi della ricerca scientifica, tecniche e modelli basati su questa rappresentazione non sono ancora stati sfruttati appieno in Bioinformatica, a causa delle sfide metodologiche e applicative poste da questa specifica disciplina. Ciononostante, in questo contesto la rappresentazione bag of words sembra essere particolarmente appropriata: da un lato, numerosi problemi bioinformatici sono inerentemente posti attraverso meccanismi di conteggio; dall'altro, in molti scenari biologici la struttura degli oggetti che li caratterizzano è assente o sconosciuta, e uno dei maggiori svantaggi della rappresentazione bag of words (che non modella tale struttura) viene a cadere. Questa tesi si inserisce nel contesto appena presentato, e promuove l'utilizzo della rappresentazione bag of words per caratterizzare oggetti e problemi in Bioinformatica e Biologia Computazionale. In questa tesi vengono investigate tutte le problematiche relative alla creazione di rappresentazioni e modelli bag of words per specifici problemi, e vengono proposte possibili soluzioni e approcci. In dettaglio, sono stati individuati ed analizzati in questa tesi tre specifici problemi bioinformatici: l'analisi dell'espressione genica, il modeling dell'infezione HIV, e l'identificazione di omologia remota fra proteine. Per ogni scenario sono state analizzate le motivazioni, i vantaggi, e le sfide poste dall'utilizzo di rappresentazioni e modelli bag of words, e sono state proposte diverse soluzioni. I meriti degli approcci proposti sono stati dimostrati attraverso estese validazioni sperimentali, sia sfruttando benchmark ampiamente utilizzati in letteratura, sia utilizzando dati derivanti dall'interazione diretta con laboratori e gruppi di ricerca clinici/biologici. La conclusione raggiunta indica che gli approcci basati sulla rappresentazione bag of words possono avere un impatto determinante nelle comunità della Bioinformatica e Biologia Computazionale.

In recent years, several Pattern Recognition problems have been successfully faced by approaches based on the "bag of words" representation. This representation is particularly appropriate when the pattern is characterized (or assumed to be characterized) by the repetition of basic, "constituting" elements called words. By assuming that all possible words are stored in a dictionary, the bag of words vector for one particular object is obtained by counting the number of times each element of the dictionary occurs in the object. Even if largely applied to several scientific fields (with increasingly sophisticated approaches), techniques based on this representation have not been completely exploited in Bioinformatics, due to the methodological and applicative challenges derived from the peculiar scenario. However, in this context the bag of words paradigm seems to be particularly suited: on one hand, many biological mechanisms inherently subsume a counting process; on the other hand, in many Bioinformatics scenarios the objects of the problem are either unstructured or with unknown structure, so that one of the main drawbacks of the bag of words representation (it destroys the object's structure) does not hold anymore. This permits to exploit and to derive highly effective and interpretable solutions, a stringent need in nowadays Bioinformatics research. This thesis is inserted in the above described scenario, and promotes the use of the bag of words paradigm to face problems in Bioinformatics. We investigated the different problematics and aspects related to the creation of bag of words models and representations for some specific Bioinformatics problems, as well as proposing original solutions and approaches based on this representation. In particular, in this thesis three scenarios have been analyzed: the gene expression analysis, the modeling of HIV infection, and the protein remote homology detection. For each scenario, motivations, advantages, and challenges of the bag of words representations are addressed, proposing possible solutions. The merits of bag of words representations and models have been demonstrated in extensive experimental evaluations, exploiting widely used benchmarks as well as datasets derived from direct interactions with biological and clinical laboratories and research groups. With this thesis, we provided evidence that the bag of words representation can have a significant impact on the Bioinformatics and Computational Biology communities.