DISTANCE BASED METHODS IN PHYLOGENETIC TREE CONSTRUCTION

摘要

One of the most fundamental aspects of bioinformatics in understanding sequence evolution and relationships is molecular phylogenetics, in which the evolutionary histories of living organisms are represented by finite directed (weighted) graphs, in particular, directed (weighted) trees. There are basically two types of phylogenetic methods, distance based methods and character based methods. Distance based methods include two clutering based algorithms, UPGMA, NJ, and two optimality based algorithms, Fitch-Margoliash and minimum evolution [7]. This paper focuses on distance based methods. The paper starts with some preliminary knowledge and definitions in the area, including finite directed graphs, directed trees and matrices. It discusses the verification of the metric property of distance matrices, including detections of errors if a distance matrix fails to satisfy the metric property, and then provides an algorithm in modifying the distance matrix to satisfy the metric property. The second part of the paper is a brief survey based on the excerpts from the references, on various frequently used distance based phylogenetic tree construction methods, both cluster-based and optimality base methods, including UPGMA, Neighbor Joining, Fitch-Margoliash, and Minimum Evolution methods. Also, it discusses the assessment of the phylogenetic trees and some analysis of the algorithms.