Please use this identifier to cite or link to this item:
Title: Algorithms for computing bidirectional best hit r-window gene clusters
Authors: Le, T.D.
Zhang, M.
Leong, H.W. 
Issue Date: 2011
Citation: Le, T.D.,Zhang, M.,Leong, H.W. (2011). Algorithms for computing bidirectional best hit r-window gene clusters. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6681 LNCS : 275-286. ScholarBank@NUS Repository.
Abstract: Genome rearrangements are large-scale mutations that result in a shuffling of the genes on a genome. Despite these rearrangements, whole genome analysis of modern species has revealed sets of genes that are found close to one another in multiple species. These conserved gene clusters provide useful information on gene function and genome evolution. In this paper, we consider a novel gene cluster model called bidirectional best hit r-window (BBHRW) in which the idea is to (a) capture the "frequency of common genes" in an r-window (interval of at most r consecutive genes) of each genome and (b) to further strengthen it by the bidirectional best hit criteria. We define two variants of BBHRW using two different similarity measures to define the "frequency of common genes" in two r-windows. Then the algorithmic problem is as follows: Give two genomes of length n and m, and an integer r, compute all the BBHRW clusters. A straight-forward algorithm for solving this problem is an O(nm) algorithm that compares all pairs of r-windows. In this paper, we present faster algorithms (SWBST and SWOT) for solving these two BBHRW variants. Algorithm SWBST is a simpler algorithm that solves the first variant of the BBHRW, while algorithm SWOT solves both variants of the BBHRW. Both algorithms have running time O((n+m)r lg r). The algorithmic speed-up is achieved via a sliding window approach and with the use of efficient data structures. We implemented the algorithms and compare their running times for finding BBHRW clusters conserved in E. coli K-12 (2339 genes) and B. subtilis (2332 genes) with r from 1 to 30 to illustrate the speed-up achieved. We also compare the two similarity measures for these genomes to show that the choice of similarity measure is an important factor for this cluster model. © 2011 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISBN: 9783642212031
ISSN: 03029743
DOI: 10.1007/978-3-642-21204-8_30
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Oct 13, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.