Linear-time algorithms for the multiple gene duplication problems

Cheng-Wei Luo; Ming-Chiang Chen; Yi-Ching Chen; Roger W L Yang; Hsiao-Fei Liu; Kun-Mao Chao

doi:10.1109/TCBB.2009.52

Linear-time algorithms for the multiple gene duplication problems

IEEE/ACM Trans Comput Biol Bioinform. 2011 Jan-Mar;8(1):260-5. doi: 10.1109/TCBB.2009.52.

Authors

Cheng-Wei Luo¹, Ming-Chiang Chen, Yi-Ching Chen, Roger W L Yang, Hsiao-Fei Liu, Kun-Mao Chao

Affiliation

¹ Department of Computer Science and Information Engineering, National Taiwan University, No. 1, Sec. 4, Roosevelt Road, Taipei 106, Taiwan. b89902079@ntu.edu.tw

PMID: 21071814
DOI: 10.1109/TCBB.2009.52

Abstract

A fundamental problem arising in the evolutionary molecular biology is to discover the locations of gene duplications and multiple gene duplication episodes based on the phylogenetic information. The solutions to the MULTIPLE GENE DUPLICATION problems can provide useful clues to place the gene duplication events onto the locations of a species tree and to expose the multiple gene duplication episodes. In this paper, we study two variations of the MULTIPLE GENE DUPLICATION problems: the EPISODE-CLUSTERING (EC) problem and the MINIMUM EPISODES (ME) problem. For the EC problem, we improve the results of Burleigh et al. with an optimal linear-time algorithm. For the ME problem, on the basis of the algorithm presented by Bansal and Eulenstein, we propose an optimal linear-time algorithm.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms*
Cluster Analysis
Computational Biology / methods*
Evolution, Molecular
Gene Duplication*
Linear Models*
Models, Genetic
Phylogeny