Campus de São José do Rio Preto DIEGO HENRIQUE NEGRETTO ALGORITMOS DE APRENDIZADO SEMI-SUPERVISIONADO BASEADOS EM GRAFOS APLICADOS NA BIOINFORMÁTICA São José do Rio Preto 2016 DIEGO HENRIQUE NEGRETTO ALGORITMOS DE APRENDIZADO SEMI-SUPERVISIONADO BASEADOS EM GRAFOS APLICADOS NA BIOINFORMÁTICA Dissertação apresentada como parte dos requisitos para obtenção do título de Mestre em Ciência da Computação, junto ao Programa de Pós-Graduação em Ciência da Computação, do Instituto de Biociências, Letras e Ciências Exatas da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Campus de São José do Rio Preto. Orientador: Prof. Dr. Fabrício Aparecido Breve São José do Rio Preto 2016 DIEGO HENRIQUE NEGRETTO ALGORITMOS DE APRENDIZADO SEMI-SUPERVISIONADO BASEADOS EM GRAFOS APLICADOS NA BIOINFORMÁTICA Dissertação apresentada como parte dos requisitos para obtenção do título de Mestre em Ciência da Computação, junto ao Programa de Pós-Grad uação em Ciência da Computação, do Instituto de Biociências, Letras e Ciências Exatas da Unive rsidade Estadual Paulista “Júlio de Mesquita Filho”, Campus de São José do Rio Preto. Orientador: Prof. Dr. Fabrício Aparecido Breve Comissão Examinadora Prof. Dr. Fabrício Aparecido Breve UNESP – Rio Claro Orientador Dr. Moacir Antonelli Ponti USP – São Carlos Dr. Daniel Carlos Guimarães Pedronette UNESP – Rio Claro São José do Rio Preto 31 de março de 2016 i Agradecimentos Primeiramente a Deus, pelo dom da vida, saúde e força para passar pelas dificuldades. À minha noiva Natália, pelo amor, apoio, carinho e paciência em todos os momentos durante o processo de estudos e por estar comigo para tudo e para sempre. Ao meu pai, mãe, irmã e cunhado, que sempre me apoiaram e acreditaram em mim, pelo apoio emocional e financeiro. Ao Prof. Dr. Fabrício, orientador, que confiou em meu potencial, pela paciência, empenho e dedicação para cumprimento de nosso trabalho. A todos meus amigos do Laboratório de Evolução Molecular (LEM) da Unesp de Rio Claro: Milene, Erik, Miagui, Dayane, Suzana e prof. Maurício, que sempre ajudaram em dúvidas e me apoiaram desde a Iniciação Científica, além de terem cedido dados de suas pesquisas para a realização deste projeto. Aos meus amigos e professores Sérgio e Orlando, que sempre me apoiaram e incentivaram no caminho da pesquisa. À FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo) pelo financiamento deste projeto por meio do processo 2015/06780-3. ii “As pessoas que são loucas o suficiente para achar que podem mudar o mundo, são as que, de fato, o mudam.” (Steve Jobs) iii SUMÁRIO 1. INTRODUÇÃO ................................................................................................ 14 1.1 Objetivos e Motivações .................................................................................. 16 1.2 Organização dos Capítulos ............................................................................. 17 2. BIOINFORMÁTICA ....................................................................................... 19 2.1 Problemas Biológicos Selecionados ............................................................... 19 2.1.1. Predição da Localização Celular de Proteínas de Levedura ....................... 21 2.1.2. Predição da Localização Celular de Proteínas na bactéria E. coli .............. 23 2.1.3. Classificação de Enzimas Digestivas de formigas da espécie Mycocepurus goeldii 25 3. APRENDIZADO DE MÁQUINA ................................................................... 28 3.1 Algoritmos de Aprendizado Supervisionado Selecionados ............................ 29 3.1.1. Support Vector Machines (SVM) ............................................................... 30 3.1.2. Árvores de Decisão ..................................................................................... 35 3.1.3. Algoritmo C4.5............................................................................................ 37 3.2 Aprendizado de Máquina Semi-Supervisionado Aplicado à Bioinformática e Algoritmos Selecionados ...................................................................................................... 39 3.2.1 Algoritmos Baseados em Grafos e Técnicas Selecionadas ......................... 40 3.2.2 Modelo de Competição e Cooperação entre Partículas ............................... 44 3.2.3 Label Propagation....................................................................................... 49 3.2.4 Label Neighborhood Propagation .............................................................. 51 3.2.5 Local and Global Consistency .................................................................... 53 4. MÉTODOS DE AVALIAÇÃO DE DESEMPENHO DE CLASSIFICADORES ............................................................................................................ 56 4.1 Método Hold-out ............................................................................................. 56 4.2 Precisão e Revocação ...................................................................................... 56 iv 4.3 Coeficiente Kappa .......................................................................................... 57 5. METODOLOGIA DE TRABALHO .............................................................. 59 5.1 Algoritmos Estudados ..................................................................................... 59 5.2 Implementação dos Algoritmos ...................................................................... 59 5.3 Bases de Dados ............................................................................................... 60 5.4 Configurações das Bases de Dados para Treinamento e Testes e Otimização dos Parâmetros ...................................................................................................................... 60 5.5 Redução de Dimensionalidade com Principal Component Analysis (PCA) .. 61 6. EXPERIMENTOS E DISCUSSÕES .............................................................. 63 6.1 Predição da Localização Celular de Proteínas de Levedura ........................... 63 6.2 Predição da Localização Celular de Proteínas na bactéria E.coli ................... 71 6.3 Definição do dataset de Enzimas Digestivas de formigas da espécie Mycocepurus goeldii ............................................................................................................. 78 6.4 Classificação de Enzimas Digestivas de formigas da espécie Mycocepurus goeldii 80 6.4.1 Utilização do Algoritmo PCA na Base de Enzimas Digestivas de formigas da espécie Mycocepurus goeldii ........................................................................................... 88 7. CONSIDERAÇÕES FINAIS E TRABALHOS FUTUROS ......................... 95 REFERÊNCIAS .......................................................................................................... 98 v LISTA DE FIGURAS Figura 1 - Estrutura em forma de Cristal da proteína 5AEX de Saccharomyces cerevisiae Mep2 ........................................................................................................................ 20 Figura 2 - Célula de Levedura ...................................................................................... 21 Figura 3 - Bactéria E.coli .............................................................................................. 24 Figura 4 - Formiga da espécie Mycocepurus goeldii .................................................... 26 Figura 5 - Dados Linearmente Separáveis .................................................................... 31 Figura 6 - Separação Linear de duas classes com base em um hiperplano. ................. 32 Figura 7 - Dados Não Linearmente Separáveis ............................................................ 33 Figura 8 - Mapeamento de Amostras do Espaço de Entrada para o Espaço de Características ........................................................................................................................... 34 Figura 9- Representação de uma Árvore de Decisão .................................................... 35 Figura 10 - Exemplos de Grafos ................................................................................... 41 Figura 11 - Representações de grafos ........................................................................... 42 Figura 12 - Dinâmica de Partículas e Nós .................................................................... 45 Figura 13- Classificação de um problema com duas classses em forma de banana por métodos tradicionais ................................................................................................................. 53 Figura 14 - Classificação de um problema com duas classes em forma de banana pelo algoritmo Local and Global Consistency ................................................................................. 54 Figura 15 - Acurácia dos algoritmos aplicados à Yeast Dataset................................... 64 Figura 16 - Valores do Coeficiente de Precisão Obtidos pelos Algoritmos na base Yeast Dataset ............................................................................................................................ 66 Figura 17- Valores do Coeficiente de Revocação Obtidos pelos Algoritmos na base Yeast Dataset ............................................................................................................................ 67 Figura 18- Valores do Coeficiente Kappa Obtidos pelos Algoritmos na base Yeast Dataset ...................................................................................................................................... 69 Figura 19 - Acurácia dos algoritmos aplicados à E.coli Dataset .................................. 71 Figura 20 - Valores do Coeficiente de Precisão Obtidos pelos Algoritmos na base E.coli Dataset ........................................................................................................................... 73 Figura 21- Valores do Coeficiente de Revocação Obtidos pelos Algoritmos na base E.coli Dataset ........................................................................................................................... 75 Figura 22 - Valores do Coeficiente Kappa Obtidos pelos Algoritmos na base E.coli Dataset ...................................................................................................................................... 77 vi Figura 23 - Exemplo da Saída do Software Blast2GO ................................................. 79 Figura 24 - Acurácia dos algoritmos aplicados ao Dataset Enzimas ........................... 81 Figura 25 - Valores do Coeficiente de Precisão Obtidos pelos Algoritmos na base Enzimas .................................................................................................................................... 83 Figura 26 - Valores do Coeficiente de Revocação Obtidos pelos Algoritmos na base Enzimas .................................................................................................................................... 84 Figura 27 - Valores do Coeficiente Kappa Obtidos pelos Algoritmos na base Enzimas .................................................................................................................................................. 86 Figura 28 - Acurácia dos algoritmos aplicados ao Dataset Enzimas com PCA ........... 89 Figura 29 - Valores do Coeficiente de Precisão Obtidos pelos Algoritmos na base Enzimas com PCA .................................................................................................................... 90 Figura 30- Valores do Coeficiente de Revocação Obtidos pelos Algoritmos na base Enzimas com PCA .................................................................................................................... 91 Figura 31 - Valores do Coeficiente Kappa Obtidos pelos Algoritmos na base Enzimas com PCA .................................................................................................................................. 93 vii