[pt] Uma filogenia é uma árvore que relaciona unidades taxonômicas, baseada na similaridade de seus conjuntos de características. O problema da filogenia consiste em encontrar uma filogenia com o número mínimo de passos evolutivos. O principal objetivo deste trabalho é desenvolver heurísticas híbridas para este problema. Duas estratégias são propostas. A primeira combina a metaheurística GRASP baseada em uma nova estrutura de vizinhança (k-SPR) proposta neste trabalho com um procedimento VND de busca local. A segunda estratégia híbrida combina algoritmos genéticos com uma estratégia de cruzamento inovadora, a qual é uma extensão da técnica de intensificação denominada reconexão por caminhos que foi originalmente aplicada no contexto de outras metaheurísticas, tais como busca tabu e GRASP. Os experimentos computacionais realizados sobre instâncias geradas aleatoriamente e instâncias da literatura científica mostram que os novos algoritmos são bastante robustos e que superaram os outros algoritmos existentes na literatura em termos de qualidade de solução e tempos computacionais obtidos. / [en] A phylogeny is a tree that relates taxonomic units, based on their similarities over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. The main goal of this work is to develop hybrid heuristics for this problem. Two strategies are proposed. The first combines the GRASP metaheuristic using a new neighborhood structure (k-SPR) proposed in this work with a VND local search procedure. The second hybrid strategy combines genetic algorithms with an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originally applied in the context of other metaheuristics such as tabu search and GRASP. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristics are quite robust and outperform the others algorithms in the literature in terms of solution quality and computational time.

This thesis presents a novel approach to reconstructing ancestral genomes of a number of descendant species related by a phylogeny. Traditional methods face challenges due to cycles of whole genome doubling followed by fractionation in plant lineages. In response, the thesis proposes a new approach that first accumulates a large number of candidate gene adjacencies specific to each ancestor in a phylogeny. A subset of these which to produces long ancestral contigs are chosen through maximum weight matching. The strategy results in more complete reconstructions than existing methods, and a number of quality measures are deployed to assess the results. The thesis also presents a new computational technique for estimating the ancestral monoploid number of chromosomes, involving a "g-mer" analysis to resolve a bias due to long contigs and gap statistics to estimate the number. The method is applied to a set of phylogenetically related descendant species, and the monoploid number is found to be 9 for all rosid and asterid orders. Additionally, the thesis demonstrates that this result is not an artifact of the method, by deriving a monoploid number of approximately 20 for the metazoan ancestor. The reconstructed ancestral genomes are functionally annotated and visualized through painting ancestral projections on descendant genomes and highlighting syntenic ancestor-descendant relationships. The proposed method is applied to genomes drawn from a broad range of plant orders. The Raccroche pipeline reconstructs ancestral gene orders and chromosomal contents of the ancestral genomes at all internal vertices of a phylogenetic tree, and constructs chromosomes by counting the frequencies of ancestral contig co-occurrence on the extant genomes, clustering these for each ancestor, and ordering them. Overall, this thesis presents a significant contribution to the field of ancestral genome reconstruction, offering a new approach that produces more complete reconstructions and provides valuable insights into the evolutionary process giving rise to the gene content and order of extant genomes.