Linear-Time Algorithms for the Multiple Gene Duplication Problems

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 dupli...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on computational biology and bioinformatics 2011-01, Vol.8 (1), p.260-265
Main Authors: Cheng-Wei Luo, Ming-Chiang Chen, Yi-Ching Chen, Yang, Roger W L, Hsiao-Fei Liu, Kun-Mao Chao
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Bioinformatics
Biology computing
Biomedical engineering
Chaos
Cluster Analysis
Computational Biology - methods
Computational phylogenetics
computations on discrete structures
Computer science
Evolution (biology)
Evolution, Molecular
Gene Duplication
Genomics
Linear Models
linear-time algorithm
Models, Genetic
Organisms
Phylogeny
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1545-5963
1557-9964
DOI:10.1109/TCBB.2009.52