Title: Repeats identification using improved suffix trees

Authors: Hongwei Huo, Xiaowu Wang, Vojislav Stojkovic

Addresses: School of Computer Science and Technology, Xidian University, Xi'an, Shaanxi 710071, China. ' School of Computer Science and Technology, Xidian University, Xi'an, Shaanxi 710071, China. ' Department of Computer Science, Morgan State University, Baltimore, Maryland 21251, USA

Abstract: The suffix tree data structure plays an important role in the efficient implementations of some querying algorithms. This paper presents the fast Rep(eats)Seeker algorithm for repeats identification based on the improvements of suffix tree construction. The leaf nodes and the branch nodes are numbered in different ways during the construction of a suffix tree and extra information is added to the branch nodes. The experimental results show that improvements reduce the running time of the RepSeeker algorithm without losing the accuracy. The experimental results coincide with the theoretical expectations.

Keywords: repeats identification; improved suffix trees; RepSeeker algorithm; suffix tree data structure; bioinformatics; gene sequences.

DOI: 10.1504/IJCBDD.2009.030117

International Journal of Computational Biology and Drug Design, 2009 Vol.2 No.3, pp.264 - 277

Published online: 10 Dec 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article