La compresión sin pérdidas empírica de una secuencia de datos

Área de la Ciencia:

• Teoría de la información
• Compresión de datos
• Inferencia estadística

Sus antecedentes:

• La complejidad de Kolmogorov proporciona un límite teórico incalculable para la compresión de datos sin pérdidas.
• El teorema de codificación de origen de Shannon establece la compresión promedio limitada como nH, donde n es la longitud de la secuencia y H es la entropía.
• La estimación de la probabilidad máxima (MLE) a menudo subestima el límite de compresión verdadero.

Objetivo del estudio:

• Para derivar y analizar la compresión sin pérdidas para secuencias de datos individuales.
• Investigar la óptimalidad de la distribución de probabilidad máxima normalizada (NML) para la compresión de datos.
• Extender los cálculos de compresión a los datos discretos y continuos, con aplicaciones en bioinformática.

Principales métodos:

• Utilizando la distribución de probabilidad máxima normalizada (NML), que se muestra como óptima en un sentido mínimo.
• Aplicación de la normalidad asintótica local para derivar la longitud del código asintótico para NML.
• Desarrollar un enfoque bayesiano para predecir la longitud óptima del código, lo que lleva a un código de mezcla.
• Cálculo de los límites de compresión para las secuencias de ADN que codifican proteínas utilizando diferentes modelos de análisis.

Principales resultados:

• La longitud del código NML se obtiene analíticamente como nH{\displaystyle \mathrm {θ} n} + (d/2) log{\displaystyle \mathrm {n} /2π} + log{\displaystyle \mathrm {I} \mathrm {θ} } 1/2) dθ + o{\displaystyle \mathrm {o} ^{\displaystyle \mathrm {o} ^{\mathrm {o} ^{\mathrm {o} ^{\mathrm {o} ^{\mathrm {o} ^{\mathrm {o} ^{\mathrm {o} } 1).
• Un código de mezcla, derivado a través de la predicción bayesiana, tiene una longitud de nH{\displaystyle \mathrm {θ^n} } + (d/2) log{\displaystyle \mathrm {n} }/2π) + log{\displaystyle \mathrm {I} } \mathrm {θ^n} } 1/2) w{\displaystyle \mathrm {θ^n} } + o{\displaystyle \mathrm {o} } 1).
• La compresión de secuencias de ADN se maximiza cuando el análisis se alinea con codones de aminoácidos, lo que demuestra su aplicación práctica.
• Los límites de compresión empírica mejoran con el aumento del tamaño del diccionario.

Conclusiones:

• La distribución NML proporciona un enfoque óptimo y computable para los límites de compresión de datos.
• Las fórmulas asintóticas derivadas ofrecen estimaciones precisas para la compresión de datos discretos y continuos.
• Las estrategias de análisis tienen un impacto significativo en la eficiencia de compresión, particularmente para las secuencias biológicas.
• El estudio proporciona un marco sólido para comprender y calcular los límites teóricos de compresión en varios tipos de datos.