Bilkent University
Department of Computer Engineering


Inferring Phylogenetical Tree

by Using Hierarchical Self Organizing Maps


Hayretdin Bahsi

M.S. in Computer Engineering

Supervisor: Assist. Prof. Dr. Atilla Gürsoy

Co-supervisor: Assist. Prof. Dr. Rengül Çetin Atalay

January 29, 2002


In biology, inferring phylogenetical tree is an attempt to describe the evolutionary history of today's species with the aim of finding common ancestor. Specifically in molecular biology, it is used in understanding the evolution relationships between proteins or DNA sequences. Inferring phylogenetical tree is very complicated task so that even for the input data having thirty sequences, the best tree must be chosen among 1036 possible trees. In order to find the best one in a reasonable time, various hierarchical clustering techniques exist in the literature. On the other side, it is known that Self Organizing Maps (SOM) are very successful in mapping higher dimensional inputs to two dimensional output spaces (maps) without having any priori information about input patterns. In this study, SOM maps are used iteratively for tree inference. Two different algorithms are proposed. First one is hierarchical top-down SOM method which constructs the tree from the root to the leaves. Second one uses bottom-up approach that infers the tree from the leaves to the root. The efficiency of hierarchical SOM is tested in terms of tree topology. Hierarchical SOM gives better results than the commonly used phylogeny methods such as UPGMA and Neighbor-Joining. Also this study covers possible solutions for branch length estimation problem.


DATE: April 29, 2002, Tuesday @ 13:30