Personal tools

IbPRIA'2017 - Diogo Pratas (2)


Jump to: navigation, search

Date 2017/06/23
Title On the approximation of the Kolmogorov complexity for DNA sequences
Speaker Diogo Pratas
Location Faro
Country Portugal

Abstract: The Kolmogorov complexity furnishes several ways for studying different natural processes that can be expressed using sequences of symbols from a finite alphabet, such as the case of DNA sequences. Although the Kolmogorov complexity is not algorithmically computable, it can be approximated by lossless normal compressors. In this paper, we use a specific DNA compressor to approximate the Kolmogorov complexity and we assess it regarding its normality. Then, we use it on several datasets, that are constituted by different DNA sequences, representing complete genomes of different species and domains. We show several evolution-related insights associated with the complexity, namely that, globally, archaea have higher relative complexity than bacteria and eukaryotes.