Search

Submitted by Matheus Lino de Freitas (lino.freitas@unesp.br) on 2021-11-16T04:28:50Z No. of bitstreams: 1 Mestrado_Bioinformatica_com_ficha.pdf: 1347903 bytes, checksum: 54fb2f30aae533d76718220ec2d19562 (MD5) Rejected by Elza Mitiko Sato null (elzasato@ibilce.unesp.br), reason: Solicitamos que realize correções na submissão seguindo as orientações abaixo: 01 – Na FOLHA DE ROSTO solicitamos colocar o nome do orientador completo: Ex: Prof. Dr. Geraldo Francisco Donegá Zafalon 02 – Solicitamos corrigir as Palavras-chave/keywords: iniciando com letras maiúsculas e separadas por ponto. 03 - Observamos que na ficha catalográfica você selecionou a formatação em páginas? Caso seja em páginas observar a margem, as margens devem ser: para o anverso, esquerda e superior de 3 cm e direita e inferior de 2 cm; para o verso, direita e superior de 3 cm e esquerda e inferior de 2 cm. Agora caso a impressão seja em folhas apenas corrija na ficha (f). 04 - A paginação deve ser sequencial, iniciando a contagem na FOLHA DE ROSTO e mostrando o número a partir da INTRODUÇÃO, a FICHA CATALOGRÁFICA ficará após a folha de rosto, será contada caso o trabalho seja formatado em página, se for formatado como folhas não deverá ser contada, e na ficha catalográfica o número de folhas deve ser igual ao número da última folha do trabalho. Sugerimos que siga as orientações do template para as correções, na página da Biblioteca, link: https://www.ibilce.unesp.br/#!/biblioteca/servicos-oferecidos/normalizacao/estrutura-do-trabalho-academico/ Lembramos que o arquivo depositado no Repositório deve ser igual ao impresso, o rigor com o padrão da Universidade se deve ao fato de que o seu trabalho passará a ser visível mundialmente. Agradecemos a compreensão. on 2021-11-16T13:51:44Z (GMT) Submitted by Matheus Lino de Freitas (lino.freitas@unesp.br) on 2021-11-16T17:12:35Z No. of bitstreams: 2 Mestrado_Bioinformatica_com_ficha.pdf: 1347903 bytes, checksum: 54fb2f30aae533d76718220ec2d19562 (MD5) Mestrado_Bioinformatica_com_ficha_revisada.pdf: 1347898 bytes, checksum: 1058176b28ea2a5cde20516c8ead95ef (MD5) Approved for entry into archive by Elza Mitiko Sato null (elzasato@ibilce.unesp.br) on 2021-11-16T19:40:42Z (GMT) No. of bitstreams: 1 freitas_ml_me_sjrp.pdf: 1347898 bytes, checksum: 1058176b28ea2a5cde20516c8ead95ef (MD5) Made available in DSpace on 2021-11-16T19:40:42Z (GMT). No. of bitstreams: 1 freitas_ml_me_sjrp.pdf: 1347898 bytes, checksum: 1058176b28ea2a5cde20516c8ead95ef (MD5) Previous issue date: 2021-09-08 Alinhamento múltiplo de sequências é uma das técnicas mais relevantes no contexto de bioinformática. Os sequenciadores modernos produzem um grande volume de dados que são posteriormente analisados por biólogos, biomédicos e profissionais da área genética. Devido a esse grande volume, estratégias computacionais são necessárias para auxiliar na análise dos dados, como por exemplo, os alinhamentos de sequências. A tarefa de alinhar sequências é um desafio computacional e biológico. Do ponto de vista biológico, os modelos são incompletos e não levam em consideração todos os aspectos estruturais e evolutivos das espécies. Além disso, do ponto de vista computacional, com os hardwares atuais, soluções exatas podem não ser obtidas em um tempo hábil. A alternativa prática é a utilização de heurísticas e modelos probabilísticos para se obter resultados com significância biológica, dentro de um tempo factível. Entretanto, heurísticas possuem a característica de se fixarem em pontos de máximo ou mínimo local e, deste modo, as soluções tornam-se sub-ótimas. Para amenizar esse problema recorre-se à utilização de estratégias híbridas e aplicação de estado caótico no algoritmo para deslocar a solução de um ponto no espaço de busca para outro. Portanto, o presente trabalho desenvolveu-se um novo método que, por meio de uma combinação entre as ferramentas KAlign e Clustal Ômega, produz um alinhamento inicial e efetua seu refinamento com otimização por colônia de formigas e chaotic jump. Houve a obtenção de 100% de melhores resultados quando comparados com a ferramenta MSA-GA e pelo menos 50% de melhores resultados quando comparados com as ferramentas KAlign e Clustal Ômega, para todas as famílias do benchmark utilizadas. Multiple sequence alignment is one of the most relevant techniques in the bioinformatics field. The next generation sequencing technologies produces a large volume of data that is later analised by biologists, biomedicals and geneticists. Due to this huge volume, computational effort are necessary to aid in the data analisys, as an example, for sequence alignment. The sequence alignment task is a both a computational and biological challenge. From the biological perspective, the abstract models are incomplete and it does not take into consideration every structural and evolutionary aspect of the species. Besides, from the computational perspective, with currently available hardwares, exact solutions cannot be found in reasonable time. The practical alternative is to use heuristics and probabilistic models to reach results with biological meaning in a feasible time. However, heuristics has a particular characteristic of falling in local maxima or local minima and therefore the solutions that are found could be suboptimal. In order to ease this problem, one can appel to the usage of hybrid strategies and the application of chaotic state in the algorithm to jump the solution in the search space from one point to another. Thus, this works aims to intruduce a novel method that combines the KAlign and Clustal Omega tools in order to produce a seed alignment that will later be refined by Ant Colony Optimization and Chaotic Jump. The results showed us that for every test the ACO produced better alignments than the MSA-GA tool and at least for 50% of tests the proposed method was able to improved the initial alignments produced by the KAlign and Clustal Omega tools.

Orientador: Zanoni Dias Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Uma das ferramentas mais importantes no campo da bioinformática e biologia computacional é o alinhamento múltiplo de sequências (MSA, do inglês Multiple Sequence Alignment). Sua função abrange a criação de árvores filogenéticas, identificação de motifs e domínios conservados, assim como a predição de funções das proteínas e de suas estruturas secundárias e terciárias. Algoritmos genéticos são heurísticas de busca local, utilizadas para problemas de otimização, inspirados nos conceitos da seleção natural: uma popularção de possíveis soluções é criada e iterativamente cruzada e selecionada buscando um resultado mais adequado para o problema sendo tratado. Esta dissertação descreve o estudo realizado no uso de algoritmos genéticos para a resolução do problema de alinhamento múltiplo de proteínas. Como resultado deste trabalho, duas ferramentas foram desenvolvidas: ALGAe, um ambiente para a execução de um algoritmo genético visando o alinhamento múltiplo de proteínas e o Anubis, um visualizador de alinhamentos que permite a comparação entre dois alinhamentos para o mesmo conjunto de proteínas, visando identificar as discrepâncias entre eles Abstract: MSA, that stands for Multiple Sequence Alignment, is one of the most important tools on bioinformatics and computational biology fields. Its usage includes phylogenetic trees creation, motifs and conservated domains prediction, as well as protein secondary and tertiary structure and function prediction. Genetic algorithms are heuristics for local search used on optimization problems, inspired on the natural selection concepts: a population of possible solution is created and iterativelly mate and selected in order to search for a suitable solution to the target problem. This dissertation describes the study we proceed on using genetic algorithms to solve the multiple sequence alignment problem. As results of this work, two tools were developed: ALGAe, a genetic algorithm execution environment for MSA solving, and Anubis, a multiple sequence alignment viewer that allows comparing a given MSA against a benchmark, in order to find discrepancies among them Mestrado Ciência da Computação Mestre em Ciência da Computação

Fil: Corvi, Javier Omar. Fundación Instituto Leloir. Laboratorio de Bioinformática Estructural; Argentina. Corvi, J. O. (2020). Análisis de coevolución en alineamientos múltiples de secuencias de proteínas evolucionados artificialmente. (Tesis de maestría). Universidad Nacional de Quilmes, Bernal, Argentina. El objetivo general de este trabajo es estudiar y analizar la relación entre coevolución y conservación derivados de MSAs en cuanto a su capacidad para predecir contactos en estructuras terciarias de proteínas. En este estudio proponemos dicho análisis en MSAs naturales y derivados de simulaciones computacionales utilizando el software SCPE. Nuestra principal hipótesis es que el SCPE provee una adecuada simulación del proceso evolutivo bajo la conservación de una estructura con la cual contrastar el proceso coevolutivo en los alineamientos naturales, mucho más complejos y diversos.

Submitted by Jose Augusto Sabino de Oliveira (augusto.sabino@unesp.br) on 2019-10-16T01:07:03Z No. of bitstreams: 1 02.1 Unesp___Defesa_2019.pdf: 2217976 bytes, checksum: 5413e1483d17e420355cd2e88f23953d (MD5) Approved for entry into archive by Elza Mitiko Sato null (elzasato@ibilce.unesp.br) on 2019-10-16T14:28:56Z (GMT) No. of bitstreams: 1 oliveira_jas_me_sjrp_par.pdf: 236922 bytes, checksum: 5d9ddd168cddd3214ab71afa7f8f9dac (MD5) Made available in DSpace on 2019-10-16T14:28:56Z (GMT). No. of bitstreams: 1 oliveira_jas_me_sjrp_par.pdf: 236922 bytes, checksum: 5d9ddd168cddd3214ab71afa7f8f9dac (MD5) Previous issue date: 2019-08-07 Os recentes avanços científicos e tecnológicos proporcionaram um grande aumento dos dados biológicos disponíveis para análise e técnicas manuais são inviáveis para executar a análise desses dados e, assim, a Bioinformática surgiu devido a necessidade de analisar-se esse volume de dados com ferramentas computacionais e possibilitar inferências relevantes. Neste contexto, técnicas de alinhamento de sequências são ferramentas imprescindíveis. No entanto, alinhar sequências tem alto custo computacional e neste cenário, adota-se o Alinhamento Múltiplo de Sequências no qual diversas heurísticas são adotadas para amenizar o problema do custo computacional. Uma destas é o Alinhamento Progressivo que funciona basicamente em três fases: alinhamento par a par, construção da árvore guia e o alinhamento de perfis. Diversos estudos destacam a importância da árvore guia e de refiná-la para manter as sequências mais similares em ramificações próximas e assim, produzir um resultado com melhor significância biológica. Assim, no presente trabalho apresenta-se conceitos e técnicas essenciais da Bioinformática e de construção da árvore guia e, por fim apresenta-se um método de refinamento da árvore guia aplicado em ferramentas que usam o Alinhamento Progressivo e que trabalha entre as etapas de construção da árvore guia e do profile final. O método recebe como entrada uma árvore guia e sua matriz de distâncias produzida pelo Alinhamento Progressivo, promove mudanças em suas ramificações internas e avalia se a probabilidade da árvore produzida é mais próxima da árvore verdadeira. Se probabilidade da árvore produzida é maior que a da árvore guia inicial, a nova árvore é devolvida como a árvore guia para a ferramenta de alinhamento construir o profile final, o que proporciona resultados com melhor significado biológico. Recent scientific and technological advances have provided a large increase in the biological data available for analysis and manual techniques are unfeasible to perform the analysis of this data and thus Bioinformatics arose due to the need to analyze this data volume with computational tools and enable relevant inferences. In this context, sequence alignment techniques are essential tools. However, aligning sequences has a high computational cost and in this scenario, Multiple Sequence Alignment is adopted in which several heuristics are adopted to alleviate the computational cost problem. One of these is Progressive Alignment which works basically in three phases: pairwise alignment, guide tree construction and profile alignment. Several studies highlight the importance of the guide tree and refining it to maintain the most similar sequences in close branches and thus produce a result with better biological significance. Thus, in the present work we discuss essential concepts and techniques of Bioinformatics and the construction of the guide tree and, finally, we present a method of refinement of the guide tree applied in tools that use Progressive Alignment and that works between he guide tree build step and the final profile build step. The method receives as input a guide tree and its distance matrix produced by Progressive Alignment, makes changes in its internal branches and evaluates if the probability of the produced tree is closer to the true tree. If the produced tree’s probability is greater than that of the initial guide tree, the new tree is returned as the guide tree for the alignment tool to build the final profile, which gives better biological significance results.

As proteínas evoluem ao longo do tempo, devido ao acúmulo de mutações, inserções e deleções nos genes que as codificam. Posições fortemente conservadas geralmente referem-se a resíduos que são estritamente necessários para a estrutura da proteína ou para sua função. A metodologia DRCN (Decomposition of Residue Coevolution Networks) permite estudar coevolução de resíduos em famílias de proteínas. Para tanto, consiste em cinco etapas básicas: filtragem do alinhamento, cálculo de correlações, decomposição da rede, geração de arquivos de visualização auxiliares e anotação de posições por busca automática no UniProt. As cisteíno proteases são um grande e diverso grupo de enzimas que pertencem ao clã CA e à família C1 (família da papaína) e podem ser encontradas em todos os animais e reinos de plantas bem como em muitos vírus e organismos procariotas. O presente trabalho tem como objetivo analisar e discutir a importância dos resíduos correlacionados e conservados da família das cisteíno proteases a partir do alinhamento múltiplo de sequências. Para tanto utilizamos, o software PFSTATS, que emprega a metodologia DRCN. Foram encontrados 34 resíduos correlacionados dispostos em 5 comunidades de resíduos que coevoluem. A comunidade 1 é a maior comunidade, sendo formada por 22 resíduos que coevoluem tanto por questões estruturais, como por exemplo Cys22 e Cys63 e Cys56 e Cys101, que realizam pontes dissulfeto; quanto por questões funcionais, como Pro2, Phe28, Gly35 e Tyr89, que se localizam em sítios alostéricos preditos da cruzaína. A comunidade 2 é composta por 6 resíduos, dentre eles resíduos da díade catalítica, Cys25 e His162, e resíduos Gly23 e Gly65, que coevoluem por questões estruturais. As comunidades 3, 4 e 5 possuem apenas 2 resíduos cada. O resíduo Cys155 da comunidade 3 possui importância estrutural, bem como os resíduos Val13 e Lys181 (comunidade 4) e Gln51 (comunidade 5). Os resíduos da comunidade 5, Leu48 e Gln51 possuem importância funcional e o resíduo Ser55 (comunidade 3) ainda não apresenta sua função descrita na literatura. Também foram encontrados 10 resíduos que são altamente conservados evolutivamente nessa família. Enquanto alguns resíduos, incluindo os que compõem a díade catalítica (Cys25 e His162), são conservados por questões funcionais, outros o são por questões estruturais (Ser49, Gly168, Gly189 e Gly192). Proteins evolve over time, due to the accumulation of mutations, insertions and deletions in the genes that encode them. Highly conserved positions generally refer to residues that are strictly necessary for the structure of the protein or for its function. The DRCN (Decomposition of Residue Coevolution Networks) methodology allows the study of coevolution of residues in protein families. To do this, it consists of five basic steps: filtering the alignment, calculating correlations, decomposing the network, generating auxiliary visualization files and annotating positions by automatic search in UniProt. Cysteine proteases are a large and diverse group of enzymes belonging to the CA clan and the C1 family (papain family) and can be found in all animals and plant kingdoms as well as in many viruses and prokaryotes. The present work aims to analyze and discuss the importance of correlated and conserved residues of the cysteine protease family from the multiple sequence alignment. For this, we use the PFSTATS software, which employs the DRCN methodology. There were 34 correlated residues found in 5 coevoluted communities. Community 1 is the largest community, consisting of 22 residues coevolved by structural issues, such as Cys22 and Cys63 and Cys56 and Cys101, which carry disulfide bridges; as well as for functional issues, such as Pro2, Phe28, Gly35 and Tyr89, which are located in predicted allosteric sites of cruzain. Community 2 is composed of 6 residues, among them residues of the catalytic dyad, Cys25 and His162, and residues Gly23 and Gly65, which coevolve for structural reasons. Communities 3, 4 and 5 have only 2 residues each. The Cys155 residue of community 3 has structural importance, as well as residues Val13 and Lys181 (community 4) and Gln51 (community 5). The residues of community 5, Leu48 and Gln51 have functional importance and the residue Ser55 (community 3) still does not present its function described in the literature. Also 10 residues were found that are highly conserved evolutionarily in this family. While some residues, including those that make up the catalytic dyad (Cys25 and His162), are conserved for functional reasons, others are for structural reasons (Ser49, Gly168, Gly189 and Gly192).

Submitted by Anderson Rici Amorim null (anderson.rici@sjrp.unesp.br) on 2017-03-31T14:22:40Z No. of bitstreams: 1 dissertacao_com ficha.pdf: 1324008 bytes, checksum: 62a964f04d4ef08c3778e88e02f8bc16 (MD5) Approved for entry into archive by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br) on 2017-04-06T17:47:08Z (GMT) No. of bitstreams: 1 amorim_ar_me_sjrp_par.pdf: 284568 bytes, checksum: 10ac089781d2f84a404d9eb932a40f48 (MD5) Made available in DSpace on 2017-04-06T17:47:08Z (GMT). No. of bitstreams: 1 amorim_ar_me_sjrp_par.pdf: 284568 bytes, checksum: 10ac089781d2f84a404d9eb932a40f48 (MD5) Previous issue date: 2017-03-03 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Com a crescente na quantidade de dados genômicos disponíveis, o alinhamento de sequências destaca-se como uma das tarefas relevantes no contexto da Bioinformática, cujos resultados são utilizados no auxílio às análises e posteriores inferências sobre esses dados. Assim, diversos algoritmos para alinhamento múltiplo de sequências baseados em diferentes heurísticas, como a de Algoritmos Genéticos, Otimização por Colônia de Formigas, Recozimento Simulado (Simulated Annealling), Busca Tabu, entre outros, foram propostos. No entanto, estudos apontam que com o uso de uma função objetivo mais adequada para aferir a qualidade do alinhamento produzido em cada caso específico, geralmente, produzem-se resultados com maior significância biológica. Além disso, o uso simultâneo de diferentes heurísticas para alinhamento múltiplo de sequências também tende a produzir melhores resultados, de modo que essa hibridização amenize as desvantagens de cada estratégia. No presente trabalho, implementou-se um escalonador automático de funções objetivo para selecionar o modelo de avaliação mais adequado para cada caso, com base na similaridade das sequências de entrada. Além disso, foi implementada uma fase de pós processamento com Otimização por Colônia de Formigas junto à MSA-GA, a fim de se refinar os alinhamentos produzidos pela ferramenta. Nos testes, pode-se verificar que o escalonador foi capaz de calcular de maneira adequada a similaridade dos conjuntos de entrada e, com isso, selecionar automaticamente a função objetivo mais apropriada. Além disso, com a execução da etapa de pós processamento, conseguiu-se refinar os alinhamentos produzidos pela MSA-GA, de modo a se obter resultados mais precisos. Due the increasing of the genomic data available, the multiple sequence alignment became one of the most important tasks in Bioinformatics, whose results are used to help biologists in their analysis. Thus, many algorithms to perform multiple sequence alignment based on different heuristics have been proposed, as Genetic Algorithms, Ant Colony, Simulated Annealing, Tabu Search, among others. Nonetheless, studies show that the use of an objective function suited for each case, generally, results in alignments with more biological significance. Moreover the simultaneous use of different heuristics to perform multiple sequence alignment can produce better results, smoothing the disadvantages of each strategy. In the present work, it was developed an automatic scheduler of objective functions to select the evaluation model more suited for each case, based on the similarity of the input sequences. Moreover it was implemented into the MSA-GA tool a post-processing stage with Ant Colony, in order to refine the obtained alignments. In the tests, it can be noticed that the scheduler calculates satisfactorily the similarity of the sequence sets and selects the more suited objective function. Moreover, with the post-processing stage, it was possible to refine the alignments of the MSA-GA, producing better results in terms of biological significance.

Submitted by Juliano Farias da Nobrega null (juliano@e8.com.br) on 2016-04-13T15:21:20Z No. of bitstreams: 1 dissert_juliano_unesp.pdf: 1652677 bytes, checksum: 2d05540d73450af0ce70d07689eeac2a (MD5) Rejected by Felipe Augusto Arakaki (arakaki@reitoria.unesp.br), reason: Solicitamos que realize uma nova submissão seguindo as orientações abaixo: O arquivo submetido está sem a ficha catalográfica. A versão submetida por você é considerada a versão final da dissertação/tese, portanto não poderá ocorrer qualquer alteração em seu conteúdo após a aprovação. Corrija esta informação e realize uma nova submissão contendo o arquivo correto. Agradecemos a compreensão. on 2016-04-14T20:43:40Z (GMT) Submitted by Juliano Farias da Nobrega null (juliano@e8.com.br) on 2016-04-15T13:45:15Z No. of bitstreams: 1 Dissertacao_Juliano_Unesp.pdf: 1798501 bytes, checksum: 97b5fd5aa56bbac1dd28b2e73b516bd4 (MD5) Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-04-18T13:22:17Z (GMT) No. of bitstreams: 1 nobrega_jf_me_sjrp.pdf: 1798501 bytes, checksum: 97b5fd5aa56bbac1dd28b2e73b516bd4 (MD5) Made available in DSpace on 2016-04-18T13:22:17Z (GMT). No. of bitstreams: 1 nobrega_jf_me_sjrp.pdf: 1798501 bytes, checksum: 97b5fd5aa56bbac1dd28b2e73b516bd4 (MD5) Previous issue date: 2016-02-29 Recentemente, a bioinformática tornou-se um recurso imprescindível para a análise e interpretação da grande quantidade de informação biológica gerada pela biologia molecular e pelos sequenciadores de última geração. O processo de comparação dessas biossequências é o ponto de partida para o estudo da evolução e diferenciação dos organismos vivos, além de ser uma das tarefas mais importantes na biologia computacional. Neste trabalho apresenta-se uma abordagem baseada na heurística de Cadeias de Markov para otimização de um algoritmo de alinhamento múltiplo de sequências biológicas, proporcionando resultados com mais qualidade e sem o comprometimento do desempenho da ferramenta MUSCLE, escolhida para dar suporte ao trabalho. As cadeias de Markov foram escolhidas como técnica de otimização devido sua eficiente aplicabilidade em diversos problemas, sobretudo na biologia computacional, pois sua metodologia probabilística torna a aplicação computacionalmente viável, contornando os problemas NP-difícil e apresentando resultados significamente precisos. Recently, bioinformatics has become an indispensable tool for analyzing and interpreting large amounts of information biological generated by molecular biology and the next-generation sequencers. The comparison process these sequences is the starting point for the study of evolution and differentiation of living organisms as well as being one of the most important tasks in computational biology. This work presents an approach based on Markov chains heuristics for optimization of a multiple alignment algorithm of biological sequences, provides improved quality results and without compromising the performance of MUSCLE tool chosen to support the work.. Markov chains were chosen as optimization technique due to its efficient applicability in various other problems, especially in computational biology, as its probabilistic methodology makes applying computationally feasible, bypassing the NP-hard problems and stating significantly accurate results.

Mestrado em Bioquímica As espécies da família Botryosphaeriaceae são morfologicamente diversas e descritas como endofíticas, patogénias e saprófitas. Estas são normalmente encontradas numa grande diversidade de hospedeiros. Os fungos patogénicos para plantas Macrophomina phaseolina, Neofusicoccum parvum e Diplodia corticola secretam uma variedade de enzimas extracelulares, tais como proteases e glicosil hidrolases, algumas das quais envolvidas na interação hospedeiro-patogénio. A fim de elucidar a correlação entre microrganismo secretoma-hospedeiro, foi comparado entre estes organismos a quantidade de sequências que codificam para enzimas tais como proteases extracelulares e glicosil hidrolases (xilanases e endoglucanases). Através de ferramentas bioinformáticas, tais como, Clustal X2 e T-Coffee, foi realizado o alinhamento múltiplo de sequências dos domínios das proteínas. Além disso, para estudar a relação evolutiva entre as sequências de proteínas foram construídas árvores filogenéticas utilizando a ferramenta MEGA. Entre M. phaseolina, N. parvum e D. corticola, o genoma de D. corticola contém genes que codificam para uma maior diversidade de famílias glicosil hidrolases sugerindo uma melhor capacidade de adaptação durante sua interação com espécies hospedeiras. A similaridade de sequências observada no alinhamento múltiplo de sequências entre M. phaseolina, N. parvum e D. corticola é explicado pela sua relação evolutiva e não pelo hospedeiro de cada um. A análise filogenética demonstra que a nível evolutivo, M. phaseolina e D. corticola estão mais próximos entre si do que a N. parvum. Species of the Botryosphaeriaceae family are morphologically diverse and are described as endophytes, pathogens and saprophytes. They are commonly found in a wide range of hosts. The plant pathogenic fungi Macrophomina phaseolina, Neofusicoccum parvum and Diplodia corticola secrete a variety of extracellular enzymes, such as proteases and glycoside hydrolases, some of which are involved in host-pathogen interaction. In order to elucidate the correlation microorganism secretome-host, the amount of sequences encoding extracellular enzymes such as proteases and glycoside hydrolase (xylanases and endoglucanases) was compared between organisms. Through bioinformatics tools, namely Clustal X2 and T-Coffee, multiple sequence alignment of the protein domains was performed. Furthermore, to study the phylogenetic relationship between protein sequences, phylogenetic trees were constructed using MEGA tool. Between M. phaseolina, N. parvum and D. corticola, D. corticola genome contains genes that encode a larger diversity of glycoside hydrolase families suggesting a better capacity for adaptability during its interaction with host species. The sequence similarity observed in the multiple sequence alignment between M. phaseolina, N. parvum and D. corticola is explained by the evolutionary relationship and not by their host type. The phylogenetic analysis shows that at the evolutionary level, M. phaseolina and D. corticola are closer to each other than to N. parvum.

Orientador: Zanoni Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Alinhamento de seqüências é, reconhecidamente, uma das tarefas de maior importância em bioinformática. Tal importância origina-se no fato de ser uma operação básica utilizada por diversos outros procedimentos na área, como busca em bases de dados, visualização do efeito da evolução em uma família de proteínas, construção de árvores filogenéticas e identificação de motifs preservados. Seqüências podem ser alinhadas aos pares, problema para o qual já se conhece algoritmo exato com complexidade de tempo O(l2), para seqüências de comprimento l. Pode-se também alinhar simultaneamente três ou mais seqüências, o que é chamado de alinhamento múltiplo de seqüências (MSA, do inglês Multiple Sequence Alignment ). Este, que é empregado em tarefas como detecção de padrões para caracterizar famílias protéicas e predição de estruturas secundárias e terciárias de proteínas, é um problema NP - Difícil. Neste trabalho foram desenvolvidos métodos heurísticos para alinhamento múltiplo de seqüências de proteína. Estudaram-se as principais abordagens e métodos existentes e foi realizada uma série de implementações e avaliações. Em um primeiro momento foram construídos 342 alinhadores múltiplos utilizando a abordagem progressiva. Esta, que é uma abordagem largamente utilizada para construção de MSAs, consiste em três etapas. Na primeira delas é computada a matriz de distâncias. Em seguida, uma árvore guia é gerada com base na matriz e, finalmente, o MSA é construído através de alinhamentos de pares, cuja ordem é definida pela árvore. Os alinhadores desenvolvidos combinam diferentes métodos aplicados a cada uma das etapas. Para a computação das matrizes de distâncias foram desenvolvidos dois métodos, que são capazes também de gerar alinhamentos de pares de seqüências. Um deles constrói o alinhamento com base em alinhamentos locais e o outro utiliza uma função logarítmica para a penalização de gaps. Foram utilizados ainda outros métodos disponíveis numa ferramenta chamada PHYLIP. Para a geração das árvores guias, foram utilizados os métodos clássicos UPGMA e Neighbor Joining. Usaram-se implementações disponíveis em uma ferramenta chamada R. Já para a construção do alinhamento múltiplo, foram implementados os métodos seleção por bloco único e seleção do par mais próximo. Estes, que se destinam a seleção xiii do par de alinhamentos a agrupar no ciclo corrente, são comumente utilizados para tal tarefa. Já para o agrupamento de um par de alinhamentos, foram implementados 12 métodos inspirados em métodos comumente utilizados - alinhamento de consensos e alinhamento de perfis. Foram feitas todas as combinações possíveis entre esses métodos, resultando em 342 alinhadores. Eles foram avaliados quanto à qualidade dos alinhamentos que geram e avaliou-se também o desempenho dos métodos, utilizados em cada etapa. Em seguida foram realizadas avaliações no contexto de alinhamento baseado em consistência. Nesta abordagem, considera-se MSA ótimo aquele que estão de acordo com a maioria dos alinhamentos ótimos para os n(n ? 1)/2 alinhamentos de pares contidos no MSA. Alterações foram realizadas em um alinhador múltiplo conhecido, MUMMALS, que usa a abordagem. As modificações foram feitas no método de contagem k-mer, assim como, em outro momento, substituiu-se a parte inicial do algoritmo. Foram alterados os métodos para computação da matriz de distâncias e para geração da árvore guia por outros que foram bem avaliados nos testes realizados para a abordagem progressiva. No total, foram implementadas e avaliadas 89 variações do algoritmo original do MUMMALS e, apesar do MUMMALS já produzir alinhamentos de alta qualidade, melhoras significativas foram alcançadas. O trabalho foi concluído com a implementação e a avaliação de algoritmos iterativos. Estes se caracterizam pela dependência de outros alinhadores para a produção de alinhamentos iniciais. Ao alinhador iterativo cabe a tarefa de refinar tais alinhamentos através de uma série de ciclos até que haja uma estabilização na qualidade dos alinhamentos. Foram implementados e avaliados dois alinhadores iterativos não estocásticos, assim como um algoritmo genético (GA) voltado para a geração de MSAs. Nesse algoritmo genético, implementado na forma de um ambiente parametrizável para execução de algoritmos genéticos para MSA, chamado ALGAe, foram realizadas diversas experiências que progressivamente elevaram a qualidade dos alinhamentos gerados. No ALGAe foram incluídas outras abordagens para construção de alinhamentos múltiplos, tais como baseada em blocos, em consenso e em modelos. A primeira foi aplicada na geração de indivíduos para a população inicial. Foram implementados alinhadores baseados em blocos usando duas abordagens distintas e, para uma delas, foram implementadas cinco variações. A segunda foi aplicada na definição de um operador de cruzamento, que faz uso da ferramenta M-COFFEE para realizar alinhamentos baseados em consenso a partir de indivíduos da população corrente do GA, e a terceira foi utilizada para definir uma função de aptidão, que utiliza a ferramenta PSIPRED para predição das estruturas secundárias das seqüências. O ALGAe permite a realização de uma grande variedade de novas avaliações Abstract: Sequence alignment is one the most important tasks of bioinformatics. It is a basic operation used for several procedures in that domain, such as sequence database searches, evolution effect visualization in an entire protein family, phylogenetic trees construction and preserved motifs identification. Sequences can be aligned in pairs and generate a pairwise alignment. Three or more sequences can also be simultaneously aligned and generate a multiple sequence alignment (MSA). MSAs could be used for pattern recognition for protein family characterization and secondary and tertiary protein structure prediction. Let l be the sequence length. The pairwise alignment takes time O(l2) to build an exact alignment. However, multiple sequence alignment is a NP-Hard problem. In this work, heuristic methods were developed for multiple protein sequence alignment. The main approaches and methods applied to the problem were studied and a series of aligners developed and evaluated. In a first moment 342 multiple aligners using the progressive approach were built. That is a largely used approach for MSA construction and is composed by three steps. In the first one a distance matrix is computed. Then, a guide tree is built based on the matrix and finally the MSA is constructed through pairwise alignments. The order to the pairwise alignments is defined by the tree. The developed aligners combine distinct methods applied to each of steps. Then, evaluations in the consistency based alignment context were performed. In that approach, a MSA is optimal when agree with the majority along all possible optimal pairwise alignments. MUMMALS is a known consistency based aligner. It was changed in this evaluation. The k-mer counting method was modified in two distinct ways. The k value and the compressed alphabet were ranged. In another evaluation, the k-mer counting method and guide tree construction method were replaced. In the last stage of the work, iterative algorithms were developed and evaluated. Those methods are characterized by other aligner's dependence. The other aligners generate an initial population and the iterative aligner performs a refinement procedure, which iteratively changes the alignments until the alignments quality are stabilized. Several evaluations were performed. However, a genetic algorithm for MSA construction stood out along this stage. In that aligner were added other approaches for multiple sequence alignment construction, such as block based, consensus based and template based. The first one was applied to initial population generation, the second one was used for a crossover operator creation and the third one defined a fitness function Doutorado Ciência da Computação Doutor em Ciência da Computação

Orientador: Zanoni Dias Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O alinhamento múltiplo dc sequências é uma tarefa de grande relevância cm Bioin-formática. Através dele é possível estudar eventos evolucionários c restrições estruturais ou funcionais, sejam de sequências de proteína, DNA ou RNA, tornando possível entender a estrutura, função c evolução dos genes que compõem um organismo. O objetivo do alinhamento múltiplo é a melhor representação do cenário dc evolução das sequencias ao longo do tempo, considerando a possibilidade dc ocorrerem diferentes eventos de mutação. Encontrar um alinhamento múltiplo dc sequencias ótimo é um problema NP-Difícil. Desta forma, diversas abordagens têm sido desenvolvidas no intuito de encontrar uma solução heurística que represente da melhor maneira possível o cenário dc evolução real, dentre elas está a abordagem progressiva. O alinhamento progressivo c uma das maneiras mais simples dc se realizar o alinhamento múltiplo, pois utiliza pouco tempo c memória computacional. Ele c realizado cm três etapas principais: determinar a distância entre as sequências que serão alinhadas, construir uma árvore guia a partir das distâncias c finalmente construir o alinhamento múltiplo. Este trabalho foi desenvolvido a partir do estudo de diferentes métodos para realizar cada etapa dc um alinhamento progressivo. Foram construídos 342 alinhadores resultantes da combinação dos métodos estudados. Os parâmetros dc entrada adequados para a maioria dos alinhadores foram determinados por estudos empíricos. Após a definição dos parâmetros adequados para cada tipo dc ahnhador, foram realizados testes com dois subconjuntos de referencia do BAliBASE. Com esses testes observamos que os melhores alinhadores foram aqueles que utilizam o agrupamento dc perfil para gerar o alinhamento múltiplo, com destaque paTa os que utilizam pontuação afim para penalizar buracos. Observamos também, que dentre os alinhadores dc agrupamento por consenso, os que utilizam função logarítmica, para penalizar buracos demonstraram melhores desempenhos Abstract: The multiple sequence alignment is a relevant task in Bioinf'ormatics. Using this technique is possible to study evolutionary events and also structural or functional restrictions of protein, DNA, or RNA sequences. This study helps the understanding of the structure, function, and evolution of the genes that make up an organism. The multiple sequence alignment tries to achieve the best representation of a sequence evolution scenario, considering different mutation events occurrence. Finding an optimal multiple sequence alignment is a NP-Hard problem. Thus, several approaches have been developed in order to find an heuristic solution that represents the real evolution cenário, such as the progressive approach. The progressive alignment is a simple way to perform the multiple alignment, because its low memcny usage and computational time. It is performed in three main stages: (i) determining the distance between the sequences to be aligned, (ii) constructing a guide tree from the distances and finally (hi) building the multiple alignment guided by the tree. This work studied different methods for performing each step of progressive alignment and 342 aligners were built combining these methods. The input parameters suitable for most aligners were determined by empirical studies. After the parameters definition for each type of aligner, which where tested against two reference subsets of BAliBASE. The test results showed that the best aligners were those using the profile alignment to generate the multiple alignment, especially those using affine gap penalty function. In addition, this work shows that among the aligners of grouping by consensus, those that use the logarithmic gap penalty function presented better performance Mestrado Bioinformática Mestre em Ciência da Computação

Mestrado em Bioquímica Submitted by Cristina Santos (cmaria@ua.pt) on 2017-05-03T10:18:44Z No. of bitstreams: 1 Tese mestrado - Ana Rita Almeida Pinheiro.pdf: 4521661 bytes, checksum: 88f5fa90a812326a8305d57b2d3bfb7a (MD5) Made available in DSpace on 2017-05-03T10:18:44Z (GMT). No. of bitstreams: 1 Tese mestrado - Ana Rita Almeida Pinheiro.pdf: 4521661 bytes, checksum: 88f5fa90a812326a8305d57b2d3bfb7a (MD5) Previous issue date: 2015