title: Whole genome/proteome based phylogeny reconstruction for prokaryotes using higher order Markov model and chaos game representation.
abstract: Traditional methods for sequence comparison and phylogeny reconstruction rely on pair wise and multiple sequence alignments. But alignment could not be directly applied to whole genome/proteome comparison and phylogenomic studies due to their high computational complexity. Hence alignment-free methods became popular in recent years. Here we propose a fast alignment-free method for whole genome/proteome comparison and phylogeny reconstruction using higher order Markov model and chaos game representation. In the present method, we use the transition matrices of higher order Markov models to characterize amino acid or DNA sequences for their comparison. The order of the Markov model is uniquely identified by maximizing the average Shannon entropy of conditional probability distributions. Using one-dimensional chaos game representation and linked list, this method can reduce large memory and time consumption which is due to the large-scale conditional probability distributions. To illustrate the effectiveness of our method, we employ it for fast phylogeny reconstruction based on genome/proteome sequences of two species data sets used in previous published papers. Our results demonstrate that the present method is useful and efficient.
  
  
  METHODS
  The source codes for our algorithm to get the distance matrix and genome/proteome sequences can be downloaded from ftp://121.199.20.25/. The software Phylip and EvolView we used to construct phylogenetic trees can be referred from their websites.
authors.affiliation: Hunan Key Laboratory for Computation and Simulation in Science and Engineering and Key Laboratory of Intelligent Computing and Information Processing of Ministry of Education, Xiangtan University, Hunan 411105, PR China; Department of Mathematics and Physics, Hunan Institute of Engineering, Hunan 411104, PR China. Electronic address: yangweifeng09@163.com.
authors.forename: Wei-Feng
authors.initials: WF
authors.lastname: Yang
authors.affiliation: Hunan Key Laboratory for Computation and Simulation in Science and Engineering and Key Laboratory of Intelligent Computing and Information Processing of Ministry of Education, Xiangtan University, Hunan 411105, PR China; School of Mathematical Sciences, Queensland University of Technology, GPO Box 2434, Brisbane, QLD 4001, Australia. Electronic address: yuzuguo@aliyun.com.
authors.forename: Zu-Guo
authors.initials: ZG
authors.lastname: Yu
authors.affiliation: School of Mathematical Sciences, Queensland University of Technology, GPO Box 2434, Brisbane, QLD 4001, Australia. Electronic address: v.anh@qut.edu.au.
authors.forename: Vo
authors.initials: V
authors.lastname: Anh
mesh_terms: D000465:Algorithms; D016678:Genome / Q000235:genetics*; D008390:Markov Chains; D017711:Nonlinear Dynamics; D010802:Phylogeny; D011387:Prokaryotic Cells / Q000378:metabolism*; D020543:Proteome / Q000235:genetics*; D016415:Sequence Alignment; D012984:Software
chemical_list: D020543:Proteome
keywords: Alignment-free whole proteome comparison; Chaos game representation; Higher order Markov model; Phylogenetic tree; Shannon entropy