Covers fundamental computational problems for the fields of comparative genomics and evolutionary biology. Specific topics include multiple sequence alignment and the reconstruction of evolutionary histories (phylogenetic trees as well as phylogenetic networks, admixture graphs, and ancestral recombination graphs). These tasks are often based on NP-hard optimization problems, motivating the development of heuristics based on discrete optimization, graph algorithms, and more recently machine learning. We analyze these algorithms from the empirical and theoretical perspectives, considering computational complexity, optimality guarantees, and statistical consistency under popular models of evolution. Lastly, we discuss emerging applications of these algorithms, from the evolution of tumors to viruses like SARS-CoV-2, as well as limitations and directions for future research.