6533b821fe1ef96bd127aedc
RESEARCH PRODUCT
Efficient Algorithms for Sequence Analysis with Entropic Profiles
Mattia OrnamentiSimone SpangaroSimona E. RomboCinzia PizziLaxmi Paridasubject
0301 basic medicineCompressed suffix arrayTheoretical computer scienceEntropySuffix tree0206 medical engineeringGeneralized suffix tree02 engineering and technologyString searching algorithmInformation theorylaw.invention03 medical and health scienceslawGeneticsAnimalsHumansMathematicsApplied MathematicsSuffix arrayComputational BiologyDNASequence Analysis DNAData structure030104 developmental biologySuffixAlignment free Entropy Sequence analysis Sequence comparisonAlgorithms020602 bioinformaticsBiotechnologydescription
Entropy, being closely related to repetitiveness and compressibility, is a widely used information-related measure to assess the degree of predictability of a sequence. Entropic profiles are based on information theory principles, and can be used to study the under-/over-representation of subwords, by also providing information about the scale of conserved DNA regions. Here, we focus on the algorithmic aspects related to entropic profiles. In particular, we propose linear time algorithms for their computation that rely on suffix-based data structures, more specifically on the truncated suffix tree (TST) and on the enhanced suffix array (ESA). We performed an extensive experimental campaign showing that our algorithms, beside being faster, make it possible the analysis of longer sequences, even for high degrees of resolution, than state of the art algorithms. © 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-01-24 | IEEE/ACM Transactions on Computational Biology and Bioinformatics |