Abstract
Grouping genes into families of homologs (i.e. copies originating from a single ancestral gene) and reconstructing the phylogeny of each gene family is essential for a variety of annotation, evolutionary, and functional studies. The orthology (divergence by speciation) and paralogy (divergence by duplication) relationships between genes are important implications towards the functional relationships between gene copies. A popular approach for inferring these relationships is to reconcile the obtained gene tree with a species tree. The accuracy of reconciliation strongly depends on the reliability of the gene tree's topology. Topological errors in a gene tree can be caused by the inference process (e.g. noise in the underlying sequence data) or the inference method itself (e.g. heuristic results). Even a few misplaced leaves will lead to a totally different history. Therefore, a great deal of effort has been put into detecting errors and then correcting the errors in a gene tree. The focus of this thesis is the gene tree correction problem. This thesis discusses two gene tree correction problems, named, respectively, the gene orthology correction problem (GOC problem) and the clade orthology correction problem (COC problem). Let G be the given gene tree and P be the given set of errors. For the GOC problem, we give an O(|P|×log |G| + |G|)-time algorithm, which improves the previous upper bound presented by Lafond et al. from O(|P|×|G|). For the COC problem, Lafond et al. gave two efficient algorithms. The first requires O(|P|×|G|) time and finds an optimal solution that induces a reconciliation (with the given species tree) minimizing the mutation cost. The second requires O(|P|×|G|) time and finds an optimal solution that also maximizes the number of common triplets with the original gene tree. In this thesis, a new algorithm is presented. The presented algorithm requires O(|G|) time and finds an optimal solution that induces a reconciliation maximizing the number of orthologous gene pairs. Keywords: Phylogenies, Gene trees, Species trees, Reconciliations, Gene tree correction problems