Branching trees cliqueにおける部分重み付け関数の最節約拡張
宮川 幹平
A study on most-parsimonious extensions of partial assignments on a branching trees clique

Let G be a connected simple graph with a vertex set V, an edge set E. Let Gσ be a graph G with a partial assignment maps from a subset U of V into the real number R. For a given Gσ, an assignment λ from V into R such that λ(u)=σ(u) for each u in U, is called an extension of σ on G. For an extension λ of σ, we define the length Lλ(e) of an edge e={u,v} on λ by |λ(u)-λ(v)|, the length Lλ(Gσ) of Gσ on λ by Σe in E Lλ(e), respectively. Furthermore, L*(Gσ) is defined by the minimum value of Lμ(Gσ) for any extension μ of σ, and an extension λ of σ such that Lλ(Gσ)=L*(Gσ) is called an most-parsimonious extension (abbreviated to MPE) on Gσ. We call the problems on this minimization the MPE problems.

From a mathematical point of view, D. F. Robinson (1973) has introduced these problems, and shown a polynomial time algorithm on the number of vertices for obtaining a MPE. On the other hand, from a phylogenetic point of view, J. M. Farris (1970), D. L. Swofford and W. P. Maddison (1987) have dealt with the problems on completely bifurcating phylogenetic trees and shown a solution. M. Hanazawa et al. (1995) have mathematically formulated the problems for the case of which G is a tree, and presented clear algorithms for those. Note that we have a gap between the Robinson method and the Hanazawa et al. one. Therefore, M. Hanazawa and H. Narushima (1999), K. Miyakawa and H. Narushima (2008) have extended the MPR problems for the case of which G is a graph having only one cycle, called a unicycle graph, and shown a linear time algorithm for solving the problems. In this paper, we deal with the MPE problems for a graph which consists of a complete graph and some trees, called a branching trees clique, and show some propositions.

Key Words: Most-parsimonious extension(MPE) , Phylogeny, Graph theory