The Resolved Triple Method For Reconstructing Phylogenetic Tree

Phylogenetics is an important field of evolutionary biology and phylogeny study had begun early in Darwin period. Phylogeny displays the evolutionary formation history of biology. Phylogenetics analyze the evolutionary relations among species, and the basic idea is comparing the characteristics of species and believing that species have similar characteristics in the genetics which are close to each other in lineage. The research results are always represented by phylogenetic trees, which are used to describe the evolution relations between species. Extract features by modeling the biological data, then compare the features and study the evolutionary history.In recent years, quartet methods for constructing phylogenetic trees have received much attention in the computational biology community. Given a quartet of sequences{a. b, c.d.} and an phylogenetic treeT, ab\cd called resolved quartet, demonstrates that ab —path disjoins with cd—path. Resolved quartet method are based upon the fact that the topology of a phylogenetic tree T is uniquely characterized by its set Q(T). But the resolved quartet set compatible problem is NP — hard, so there is no polynomial time algorithm.In this paper we propose a resolved triple method, which can reconstruct phylogenetic tree in polynomial time and check if the resolved triple set. is compatible. Given {a.b.c} and an phylogenetic tree T, symbol ab|c is called resolved triple if there are two interior nodes{u, v}, a, b, c (?) des(u), a, b (?) des(v), c (?) des(v). Firstly we construct a directed graph G_r corresponding to resolved triple set R, then simplify the triple set R by comparing the disjoined path p_k. in G_r. at last get the base. In part 4, we prove the method by resolved quartet set, and bring up the necessary condition of compatible resolved quartet set.This thesis is composed of four chapters.Chapter 1: An introduction, state the history of question.Chapter 2: Classical conclusion and the basic, definitions, prepared knowledge, introduce the notation, related definition and the classical conclusion .Chapter 3: Compatibility of resolved triple set and a polynomial time algorithm. Not only the most important chapter, but also the center of the thesis. In this chapter, we propose a (n-2)base algorithm by analyzing the directed graph G_r.Chapter 4: Compatibility of resolved quartet set. In this chapter, firstly we prove the algorithm in Chapter 3, then bring up the necessary condition of compatible resolved quartet set.