DocumentCode :
109390
Title :
Constructing a Gene Team Tree in Almost O (n; {\\rm \\lg}; n) Time
Author :
Biing-Feng Wang ; Chien-Hsin Lin ; I-Tse Yang
Author_Institution :
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
Volume :
11
Issue :
1
fYear :
2014
fDate :
Jan.-Feb. 2014
Firstpage :
142
Lastpage :
153
Abstract :
An important model of a conserved gene cluster is called the gene team model, in which a chromosome is defined to be a permutation of distinct genes and a gene team is defined to be a set of genes that appear in two or more species, with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold δ. A gene team tree is a succinct way to represent all gene teams for every possible value of δ. The previous fastest algorithm for constructing a gene team tree of two chromosomes requires O(n lg n lglg n) time, which was given by Wang and Lin. Its bottleneck is a problem called the maximum-gap problem. In this paper, by presenting an improved algorithm for the maximum-gap problem, we reduce the upper bound of the gene team tree problem to O(n lg n α(n)). Since α grows extremely slowly, this result is almost as efficient as the current best upper bound, O(n lg n), for finding the gene teams of a fixed δ value. Our new algorithm is very efficient from both the theoretical and practical points of view. Wang and Lin´s gene-team-tree algorithm can be extended to k chromosomes with complexity O(kn lg n lglg n). Similarly, our improved algorithm for the maximum-gap problem reduces this running time to O(kn lg n α(n)). In addition, it also provides new upper bounds for the gene team tree problem on general sequences, in which multiple copies of the same gene are allowed.
Keywords :
biology computing; cellular biophysics; computational complexity; genetics; tree data structures; O(kn lg n lglg n) complexity; O(n lg n lglg n) time; chromosome; conserved gene cluster model; gene team model; gene team tree algorithm; maximum-gap problem; Algorithm design and analysis; Bioinformatics; Biological cells; Biological system modeling; Computational biology; Data structures; Upper bound; Algorithms; comparative genomics; conserved gene clusters; data structures; gene teams;
fLanguage :
English
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
Publisher :
ieee
ISSN :
1545-5963
Type :
jour
DOI :
10.1109/TCBB.2013.150
Filename :
6674301
Link To Document :
بازگشت