The historic relationship of species and genes are traditionally depicted using trees. However, not all evolutionary histories are adequately captured by bifurcating processes and an increasing amount of research is devoted towards using networks or network-like structures to capture evolutionary history. Lateral gene transfer (LGT) is a previously controversial mechanism responsible for non tree-like evolutionary histories, and is today accepted as a major force of evolution, particularly in the prokaryotic domain. In this thesis, we present models of gene evolution incorporating both LGTs and duplications, together with efficient computational methods for various inference problems. Specifically, we define a biologically sound combinatorial model for reconciliation of species and gene trees that facilitates simultaneous consideration of duplications and LGTs. We prove that finding most parsimonious reconciliations is NP-hard, but that the problem can be solved efficiently if reconciliations are not required to be acyclic—a condition that is satisfied when analyzing most real-world datasets. We also provide a polynomial-time algorithm for parametric tree reconciliation, a problem analogous to parametric sequence alignment, that enables us to study the entire space of optimal reconciliations under all possible cost schemes. Going beyond combinatorial models, we define the first probabilistic model of gene evolution incorporating a birth-death process generating duplications, LGTs, and losses, together with a relaxed molecular clock model of sequence evolution. Algorithms based on Markov chain Monte Carlo (MCMC) techniques, methods from numerical analysis, and dynamic programming are presented for various probability and parameter inference problems. Finally, we develop methods for analysis of cancer progression, a biological process with many similarities to the process of evolution. Cancer progresses by accumulation of harmful genetic aberrations whose patterns of emergence are graph-like. We develop a model of cancer progression based on trees, and mixtures thereof, that admits an efficient structural EM algorithm for finding Maximum Likelihood (ML) solutions from available cross-sectional data. / QC 20100812

Made available in DSpace on 2014-06-11T19:33:26Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-05-20Bitstream added on 2014-06-13T18:45:08Z : No. of bitstreams: 1 okamoto_as_dr_botfmvz.pdf: 316486 bytes, checksum: 9da72cf8a36b7e04e7b42adc80fe9b71 (MD5) / Universidade Estadual Paulista (UNESP) / Neste trabalho foram analisadas 100 cepas de Salmonella Enteritidis (SE) isoladas de material avícola, visando à detecção dos genes de virulência spvC e invA e resistência a antimicrobianos integron classe 1. Comparando-se com a possível expressão dos fatores de virulência para sobrevivência em condições impróprias de temperatura, pH e concentração de nutrientes e o teste de inibição em placa, respectivamente. Também a capacidade de transferência horizontal do gene integron classe 1 foi avaliada em SE. Das cepas analisadas, duas apresentaram os genes spvC e invA, simultaneamente, com uma provável expressão destes sendo verificada no crescimento com pH 10,0 ou temperatura de 25ºC. Porém em relação à concentração de nutriente, ambas as cepas não cresceram na menor concentração (0,5%). Não houve relação direta entre a presença do gene integron classe 1 com a multiresistência de SE aos 14 antimicrobianos testados, já que 80% das cepas pesquisadas foram resistentes a até três antimicrobianos e não apresentaram o referido gene. Entretanto, a transferência horizontal desse gene e da resistência antimicrobiana foi realizada in vitro, de um Escherichia coli para uma Salmonella Enteritidis, demonstrando a capacidade de disseminação do gene presente em integron classe 1. / In this work, 100 strains of Salmonella Enteritidis (SE) isolated from avian material were studied, aiming to detect the genes of virulence spvC and invA, as well as the antimicrobial resistance type 1 integron genes using the polymerase chain reaction (PCR), comparing it with the possible expression of the virulence factors to survive under inappropriate conditions of temperature, pH and nutrient concentration, and the plaque inhibition assay, respectively. Capacity of horizontal transfer of type 1 0,integron gene was also evaluated in SE. Two of the analyzed strains showed spvC and InvA genes simultaneously, with a probable expression verified through growing in pH 10.0 or 25°C temperature. However, regarding to nutrient concentration, the aforementioned strains did not grow at the lowest concentration (0.5%). There was no direct relation between type 1 integron gene and the multiresistance of SE to the 14 tested antibiotics, because 80% of the strains did not showed the gen, but was resistant till three antibiotics. However, horizontal transfer of this gene was performed in vitro, showing the capacity of dissemination of the type 1 integron gene between bacteria.

Orientador: Raphael Lucio Andreatti Filho / Banca: Edna Teresa de Lima / Banca: Noeme Sousa Rocha / Banca: Julio Lopes Sequeira / Banca: Marcelo Vasconcelos Meireles / Resumo: Neste trabalho foram analisadas 100 cepas de Salmonella Enteritidis (SE) isoladas de material avícola, visando à detecção dos genes de virulência spvC e invA e resistência a antimicrobianos integron classe 1. Comparando-se com a possível expressão dos fatores de virulência para sobrevivência em condições impróprias de temperatura, pH e concentração de nutrientes e o teste de inibição em placa, respectivamente. Também a capacidade de transferência horizontal do gene integron classe 1 foi avaliada em SE. Das cepas analisadas, duas apresentaram os genes spvC e invA, simultaneamente, com uma provável expressão destes sendo verificada no crescimento com pH 10,0 ou temperatura de 25ºC. Porém em relação à concentração de nutriente, ambas as cepas não cresceram na menor concentração (0,5%). Não houve relação direta entre a presença do gene integron classe 1 com a multiresistência de SE aos 14 antimicrobianos testados, já que 80% das cepas pesquisadas foram resistentes a até três antimicrobianos e não apresentaram o referido gene. Entretanto, a transferência horizontal desse gene e da resistência antimicrobiana foi realizada in vitro, de um Escherichia coli para uma Salmonella Enteritidis, demonstrando a capacidade de disseminação do gene presente em integron classe 1. / Abstract: In this work, 100 strains of Salmonella Enteritidis (SE) isolated from avian material were studied, aiming to detect the genes of virulence spvC and invA, as well as the antimicrobial resistance type 1 integron genes using the polymerase chain reaction (PCR), comparing it with the possible expression of the virulence factors to survive under inappropriate conditions of temperature, pH and nutrient concentration, and the plaque inhibition assay, respectively. Capacity of horizontal transfer of type 1 0,integron gene was also evaluated in SE. Two of the analyzed strains showed spvC and InvA genes simultaneously, with a probable expression verified through growing in pH 10.0 or 25°C temperature. However, regarding to nutrient concentration, the aforementioned strains did not grow at the lowest concentration (0.5%). There was no direct relation between type 1 integron gene and the multiresistance of SE to the 14 tested antibiotics, because 80% of the strains did not showed the gen, but was resistant till three antibiotics. However, horizontal transfer of this gene was performed in vitro, showing the capacity of dissemination of the type 1 integron gene between bacteria. / Doutor