Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graduação em Informática, 2016. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2016-08-03T13:45:05Z No. of bitstreams: 1 2016_JoaoVictorAraujoOliveira.pdf: 3385598 bytes, checksum: 87023d9eae07bd39a3d1cb8613c3d33f (MD5) / Approved for entry into archive by Patrícia Nunes da Silva(patricia@bce.unb.br) on 2016-12-06T13:01:15Z (GMT) No. of bitstreams: 1 2016_JoaoVictorAraujoOliveira.pdf: 3385598 bytes, checksum: 87023d9eae07bd39a3d1cb8613c3d33f (MD5) / Made available in DSpace on 2016-12-06T13:01:15Z (GMT). No. of bitstreams: 1 2016_JoaoVictorAraujoOliveira.pdf: 3385598 bytes, checksum: 87023d9eae07bd39a3d1cb8613c3d33f (MD5) / Métodos de aprendizagem de máquina vêm sendo amplamente usados na identificação e classificação de diferentes famílias de RNAs não-codificadores (ncRNAs). Muitos desses métodos são baseados na aprendizagem supervisionada, onde atributos anteriormente conhecidos, chamados features, são extraídos de uma sequência e usados em um classificador. Nesta dissertação, apresentamos dois métodos para a identificação das duas classes principais de snoRNAs, C/D box e H/ACA box snoRNAs: snoReport 2.0, uma melhoria significativa da primeira versão do snoReport; e o snoRNA-EDeN, um novo método baseado no EDeN, que é um kernel decomposicional de grafos. O snoReport 2.0 é um método que, usando features extraídas de sequências candidatas em genomas, combina predição de estrutura secundária de ncRNAs com Máquina de Vetores de Suporte (Support Vector Machine - SVM), para identificar C/D box e H/ACA box snoRNAs. Seu classificador de H/ACA box snoRNA mostrou um F-score de 93% (uma melhoria de 10% em relação à primeira versão do snoReport), enquanto o classificador de C/D box snoRNA obteve F-score de 94% (melhoria de 14%). Alem disso, ambos os classificadores tiveram todas as medidas de performances acima de 90%. Na fase de validação, o snoReport 2.0 identificou 67,43% dos snoRNAs de vertebrados de ambas as classes. Em Nematóides, o snoReport 2.0 identificou 29,6% dos C/D box snoRNAs e 69% dos H/ACA box snoRNAs. Para as Drosofilídeas, foram identificados 3,2% dos C/D box snoRNAs e 76,7% dos H/ACA box snoRNAs. Esses resultados mostram que o snoReport 2.0 é eficiente na identificação de snoRNAs em organismos vertebrados, e também para H/ACA box snoRNAs de organismos invertebrados. Por outro lado, em vez de usar features de uma sequência (em geral, difíceis de identificar), uma abordagem recente de aprendizagem de máquina é descrita a seguir. Dada uma região de interesse de uma sequencia, o objetivo é gerar um vetor esparso que pode ser usado como micro-features em algum algoritmo de aprendizado de máquina, ou pode ser usado para a criação de features poderosas. Essa abordagem é usada no EDeN (Explicit Decomposition with Neighbourhoods), um kernel decomposicional de grafos baseado na técnica Neighborhood Subgraph Pairwise Distance Kernel (NSPDK). O EDeN transforma um grafo em um vetor esparso, decompondo-o em todos os pares de subgrafos vizinhos de raios pequenos, a distâncias crescentes. Baseado no EDeN, foi desenvolvido um método chamado snoRNA-EDeN. Na fase de testes, para C/D box snoRNAs, o snoRNA-EDeN obteve um F-score de 93,4%, enquanto que para H/ACA box snoRNAs o F-score foi de 85.12%. Na fase de validação, para C/D box snoRNA, o snoRNA-EDeN mostrou uma grande capacidade de generalização, identificando 94,61% de snoRNAs de vertebrados e 63,52% de invertebrados, um resultado significantemente melhor em comparação ao snoReport 2.0, que identificou apenas 52,92% dos vertebrados e 14,6% dos invertebrados. Para o H/ACA box, o snoReport 2.0 identificou 79,9% dos snoRNAs de vertebrados e 73,3% dos snoRNAs de Nematóides e Drosofilídeos, enquanto que o snoRNA-EDeN identificou 95,4% dos vertebrados e 57.8% dos nematóides e drosofilas. Ambos os métodos estão disponíveis em: http://www.biomol.unb.br/snoreport e http://www.biomol.unb.br/snorna_eden. ___________________________________________________________________________ ABSTRACT / Machine learning methods have been widely used to identify and classify different families of non-coding RNAs. Many of these methods are based on supervised learning, where some previous known attributes, called features, are extracted from a sequence, and then used in a classifier. In this work, we present two methods to identify the two main classes of snoRNAs, C/D box and H/ACA box: snoReport 2.0, a significant improvement of the original snoReport version; and snoRNA-EDeN, a new method based on EDeN, a decompositional graph kernel. On one hand, snoReport 2.0 is a method that, using features extracted from candidate sequences in genomes, combines secondary structure prediction with Support Vector Machine (SVM) to identify C/D box and H/ACA box snoRNAs. H/ACA box snoRNA classifier showed a F-score of 93% (an improvement of 10% regarding to the previous version), while C/D box snoRNA classifier a F-Score of 94% (improvement of 14%). Besides, both classifiers exhibited performance measures above 90%. In the validation phase, snoReport 2.0 predicted 67.43% of vertebrate organisms for both classes. SnoReport 2.0 predicted: for Nematodes, 29.6% of C/D box and 69% of H/ACA box snoRNAs; and for Drosophilids, 3.2% of C/D box and 76.7% of H/ACA box snoRNAs. These results show that snoReport 2.0 is efficient to identify snoRNAs in vertebrates, and also H/ACA box snoRNAs in invertebrates organisms. On the other hand, instead of using known features from a sequence (difficult to find in general), a recent approach in machine learning is described as follows. Given a region of interest of a sequence, the objective is to generate a sparse vector that can be used as micro-features in a specific machine learning algorithm, or it can be used to create powerful features. This approach is used in EDeN (Explicit Decomposition with Neighbourhoods), a decompositional graph kernel based on Neighborhood Subgraph Pairwise Distance Kernel (NSPDK). EDeN transforms one graph in a sparse vector, decomposing it in all pairs of neighborhood subgraphs of small radius at increasing distances. Based on EDeN, we developed a method called snoRNA-EDeN. On the test phase, for C/D box snoRNAs, snoRNA-EDeN showed a F-score of 93.4%, while for H/ACA box snoRNAs, the F-score was 72%. On the validation phase, for C/D box snoRNAs, snoRNA-EDeN showed a better capacity of generalization, predicting 94.61% of vertebrate C/D box snoRNAs and 63.52% of invertebrates, a significantly better result compared to snoReport 2.0, which predicted only 52.92% of vertebrates and 14.6% of invertebrates. For H/ACA box snoRNAs, snoReport 2.0 predicted 79.9% of vertebrate snoRNAs and 73.3% of Nematode and Drosophilid sequences, while snoRNA-EDeN predicted 95.4% of vertebrate snoRNAs and 57.8% of Nematode and Drosophilid sequences. Both methods are available at http://www.biomol.unb.br/snoreport and http://www.biomol.unb.br/snorna_eden.