Leaf Ordering Optimization for Hierarchical Clustering Tree of Protein Phosphorylation Sequences

The process of protein phosphorylation plays an essential role in regulation of cellular processes including metabolism, apoptosis, membrane transportation, cellular proliferation and cellular signaling. The analysis of protein phosphorylation sites is therefore important in the research of protein functions. Data clustering methods, especially hierarchical clustering methods, have been extensively used in the analysis of gene and miRNA expression data to explore the underlying trends and relations among genes, miRNAs, or samples. Those methods use similarity measures to group similar data objects into clusters. For unknown datasets, clustering methods provide an efficient way to gain insight into the clustered data. In this research, we propose to develop an efficient model to optimize the leaf ordering of trees that are generated by hierarchical clustering on protein phosphorylation sequences. For a hierarchical clustering tree (dendrogram) with n leaves, there are 2n-1 linear orderings consistent with the branching structure of the tree. Simulated annealing algorithms have been successfully applied to many combinatorial optimization problems. We propose to use simulated annealing algorithms to efficiently find optimal leaf ordering for hierarchical clustering tree of protein phosphorylation sequences.

Project ID:PB10108-2156
External Project ID:NSC101-2221-E182-072