14. Phylogenetics

Phylogenetics is the study of evolutionary relationships among organisms. Sequence alignment is commonly performed as the first step of phylogenetics to determine the similarities of DNA and protein sequences. Searching these relationships is needed to analyze diseases, predict the genetic structures of pathogens, and also to classify the organisms. We pursue an evolutionary structure called the phylogenetic tree with leaves representing the living organisms called taxa and the intermediate nodes as the hypothetical ancestors. We start this chapter by stating the terms of phylogenetic terminology. We then describe various methods of constructing phylogenetic trees and propose a simple distributed algorithm to construct such trees. In the maximum parsimony problem, we are given the evolutionary tree and a number of taxa, and our aim is to label nodes of this tree that explains data with minimum number of mutations. We review a number of algorithms for this purpose and introduce a new algorithm for distributed parsimony implementation. After reviewing the probabilistic maximum likelihood method of constructing phylogenetic trees, we provide a brief review of distributed approaches that use maximum likelihood. Phylogenetic networks are more general as they exhibit events such as horizontal gene transfer and recombination which cannot be represented by the evolutionary trees. We discuss these networks briefly to conclude this chapter.