The present review is intended for mathematicians who wish to get acquainted with graph theory applications to one of the key problems in evolution theory: the one of reconstructing evolution history (the phylogenesis). This problem arises in biology as well as many other areas, including language studies and classical philology. The model of a phylogenetic tree we formulate underlies the practical methods of phylogenesis reconstruction. We consider an ideal representation for which the evolutionary distance matches the distance between the vertices of the sought-for phylogenetic tree, and also a more true to life situation, when the desired phylogenetic tree is substituted by a tree that corresponds best to the available dataset. One of the possible approaches for choosing a concordance criterion is to minimize a certain metric function measuring the degree of discrepancy between the matrix of evolutionary distances and the matrix of distances between the leaves of the sought-for tree. The article discusses various types of such functions and the methods of phylogenetic tree construction that are optimal for each type of function. We also describe the methods of constructing phylogenetic trees based on minimization of non-metric functions. We consider the computational complexity of construction algorithms as well as that of coordinating various phylogenetic trees that were built from a single dataset. We discuss the limitations of applying the phylogenetic tree model and the mathematical problems of constructing a more general model that would include the phylogenetic tree model as a special case.

mathematical biology, phylogenetic trees, bioinformatics, graph theory, phylogenesis

Mathematical problems and theory of numerical methods