Since the dawn of evolutionary biology, it was the dream of scientists to obtain a meaningful tree of life (a phylogenetic tree). Regarding the prokaryotic universe (Bacteria and Archaea), a main question of phylogenetics is whether there exists a prokaryotic tree of life actually. Those organisms exhibit mechanisms for the direct exchange of genetic material between cells that can belong to different species (horizontal gene transfer). In this book, the GBDP framework for inferring phylogenies based on whole genomes is introduced. Furthermore, the amount of horizontal gene transfer in a common set of prokaryotic genes is investigated by using a state-of-the-art method, as well as two newly developed approaches. Additionally, a new method for species delineation is proposed that is based on the GBDP method for deriving whole genome phylogenies. In the last part of this work, several software packages are presented. CopyCat, together with AxParafit and AxPcoords, represents the first Grid-enabled software package that is optimized for large-scale cophylogenetic studies. Furthermore, MEGAN, a user-friendly software application for the analysis of metagenomic datasets is presented.