On the Approximation of the Kolmogorov Complexity for DNA Sequences

扫码查看

原文链接

NETL
Springer Nature

外文摘要：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。

外文关键词：

Kolmogorov complexityCompressionDNA sequences

作者：

Diogo Pratas、Armando J. Pinho

展开 >

作者单位：

IEETA, University of Aveiro, 3810-193 Aveiro, Portugal

会议名称：

Iberian conference on pattern recognition and image analysis

会议地点：

Faro(PT)

会议母体文献：

Pattern recognition and image analysis

页码：

259-266

出版时间：

2017

DOI：

10.1007/978-3-319-58838-4_29