README.md 1.18 KB
Newer Older
jkvis's avatar
jkvis committed
1 2 3 4 5 6 7 8 9 10 11 12
# GESA library

This library implements Generalized Enhanched Suffix Arrays (GESAs).
ESAs (for single strings) are created using
[sais-lite-lcp](https://github.com/kurpicz/sais-lite-lcp)
(see [also](http://algo2.iti.kit.edu/english/1828.php)) [1]. In theory,
any implementation for the construction of suffix arrays and the longest
common prefix array (LCP) can be used.

GESAs are constructed from ESAs using a generalization of the merging
method from [2].

jkvis's avatar
jkvis committed
13
**NOTE** currently Algorithm 5.21 [2] is implemented with a
jkvis's avatar
jkvis committed
14
worst-case O( n^2 ) complexity. We should implement Section 5.5.5 [2],
jkvis's avatar
jkvis committed
15
which is based on [3].
jkvis's avatar
jkvis committed
16

jkvis's avatar
jkvis committed
17 18
## References
[1] J. Fischer. Inducing the LCP-Array. In F. Dehne, J. Iacono, and J. Sack, editors, *Algorithms and Data Structures: 12th International Symposium, WADS 2011, New York, USA, August 15-17, 2011. Proceedings*, pages 374-385. Springer, 2011.  
jkvis's avatar
jkvis committed
19 20
[2] E. Ohlebusch. *Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction* Oldenbusch Verlag, 2013.  
[3] J.E. Jeon, H. Park and D.K. Kim. Efficient Construction of Generalized Suffix Arrays by Merging Suffix Arrays. *Journal of KIISE: Computer Systems and Theory*, 32(6):268-278, 2005.