Composition vector method based on maximum entropy principle for sequence comparison

Raymond H. CHAN*, Tony H. CHAN, Hau Man YEUNG, Roger Wei WANG

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

18 Citations (Scopus)


The composition vector (CV) method is an alignment-free method for sequence comparison. Because of its simplicity when compared with multiple sequence alignment methods, the method has been widely discussed lately; and some formulas based on probabilistic models, like Hao's and Yu's formulas, have been proposed. In this paper, we improve these formulas by using the entropy principle which can quantify the nonrandomness occurrence of patterns in the sequences. More precisely, existing formulas are used to generate a set of possible formulas from which we choose the one that maximizes the entropy. We give the closed-form solution to the resulting optimization problem. Hence, from any given CV formula, we can find the corresponding one that maximizes the entropy. In particular, we show that Hao's formula is itself maximizing the entropy and we derive a new entropy-maximizing formula from Yu's formula. We illustrate the accuracy of our new formula by using both simulated and experimental data sets. For the simulated data sets, our new formula gives the best consensus and significant values for three different kinds of evolution models. For the data set of tetrapod 18S rRNA sequences, our new formula groups the clades of bird and reptile together correctly, where Hao's and Yu's formulas failed. Using real data sets with different sizes, we show that our formula is more accurate than Hao's and Yu's formulas even for small data sets.

Original languageEnglish
Article number5728790
Pages (from-to)79-87
Number of pages9
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number1
Publication statusPublished - 2012
Externally publishedYes


  • alignment-free sequence comparison
  • Composition vector method
  • maximum entropy principle
  • optimization model
  • phylogenetics


Dive into the research topics of 'Composition vector method based on maximum entropy principle for sequence comparison'. Together they form a unique fingerprint.

Cite this