NDLI: A Suffix Tree Construction Algorithm for DNA Sequences

Content Provider	IEEE Xplore Digital Library
Author	Huo, Hongwei Stojkovic, Vojislav
Copyright Year	2007
Description	Author affiliation: School of Computer Science and Technology, Xidian University, Xi'an 710071, China. hwhuo@mail.xidian.edu.cn (Huo, Hongwei) \|\| Computer Science Department, Morgan State University, Baltimore, MD 21251, USA. stojkovi@jewel.morgan.edu (Stojkovic, Vojislav)
Abstract	The suffix tree is a powerful data structure in string processing and DNA sequence comparisons. However, constructing suffix trees being very greedy in space is a fatal drawback. In addition, the performance of the suffix tree construction using suffix link will rapidly degrade with the increase of the scale of sequences to be handled because of the random access. In order to overcome these disadvantages, a new bit layout is used for the nodes of a suffix tree which has less space requirements. Based on this an algorithm to construct suffix tree for DNA sequences is proposed using partitioning strategies. The effectiveness for the proposed algorithm is shown in the testing cases from NCBI web site. Comparisons with Kurtz's algorithm in space requirements and running time have been made in the experiments. The results show that the proposed algorithm is memory-efficient and has a better performance over Kurtz's algorithm on the average running time.
Starting Page	1178
Ending Page	1182
File Size	927185
Page Count	5
File Format	PDF
ISBN	9781424415090
DOI	10.1109/BIBE.2007.4375711
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-10-14
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	DNA Sequences Partitioning algorithms Bioinformatics Genomics Tree data structures Computer science Binary search trees Performance loss Degradation
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Parsimony-spaced suffix trees for DNA sequences

The Suffix Tree Construction for Large Sequences over Hand-held Device

MapReduce based parallel suffix tree construction for human genome

Binary search trees for vector quantisation

An Adaptive Suffix Tree Based Algorithm for Repeats Recognition in a DNA Sequence

New algorithms for balancing binary search trees

Sparsification-a technique for speeding up dynamic graph algorithms

Randomized multidimensional search trees: further results in dynamic sampling

Binary search tree visualization algorithm

A Suffix Tree Construction Algorithm for DNA Sequences

Similar Documents

Parsimony-spaced suffix trees for DNA sequences

The Suffix Tree Construction for Large Sequences over Hand-held Device

MapReduce based parallel suffix tree construction for human genome

Binary search trees for vector quantisation

An Adaptive Suffix Tree Based Algorithm for Repeats Recognition in a DNA Sequence

New algorithms for balancing binary search trees

Sparsification-a technique for speeding up dynamic graph algorithms

Randomized multidimensional search trees: further results in dynamic sampling

Binary search tree visualization algorithm

A Suffix Tree Construction Algorithm for DNA Sequences