Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

The Enhanced Suffix Array and Its Applications to Genome Analysis

Mohamed Ibrahim AbouelhodaContact Information, Stefan KurtzContact Information and Enno OhlebuschContact Information

(6)  Faculty of Technology, University of Bielefeld, P.O. Box 10 01 31, 33501 Bielefeld, Germany
Abstract
In large scale applications as computational genome analysis, the space requirement of the suffix tree is a severe drawback. In this paper, we present a uniform framework that enables us to systematically replace every string processing algorithm that is based on a bottomup traversal of a suffix tree by a corresponding algorithm based on an enhanced suffix array (a suffix array enhanced with the lcp-table). In this framework, we will show how maximal, supermaximal, and tandem repeats, as well as maximal unique matches can be efficiently computed. Because enhanced suffix arrays require much less space than suffix trees, very large genomes can now be indexed and analyzed, a task which was not feasible before. Experimental results demonstrate that our programs require not only less space but also much less time than other programs developed for the same tasks.

Contact Information Mohamed Ibrahim Abouelhoda
Email: mibrahim@TechFak.Uni-Bielefeld.DE

Contact Information Stefan Kurtz
Email: kurtz@TechFak.Uni-Bielefeld.DE

Contact Information Enno Ohlebusch
Email: enno@TechFak.Uni-Bielefeld.DE
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
3 newer articles

  1. Jin, Victor X. (2007) . IEEE Transactions on Instrumentation and Measurement 56(5)
    [CrossRef]
  2. Horner, D. S. (2009) Bioinformatics approaches for genomics and post genomics applications of next-generation sequencing. Briefings in Bioinformatics
    [CrossRef]
  3. Maaß, Moritz G. (2006) Matching statistics: efficient computation and a new practical algorithm for the multiple common substring problem. Software Practice and Experience 36(3)
    [CrossRef]
Remote Address: 38.107.191.108 • Server: mpweb21
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)