A informação dos códigos genéticos sequenciados é na actualidade, provavelmente, a
fonte mais inspiradora para o estudo e avanço das teorias da informação e da
codificação. Algoritmos eficientes para a sua compressão antevêm-se essenciais para a
optimização do armazenamento e comunicação da informação genómica. A compressão
de informação genómica é um caso particular da compressão de informação. A entropia
das sequências de ADN é elevada, contudo variável. Ao nível intra-genómico é maior
nas regiões codificantes e menor nas regiões não codificantes. Ao nível inter-genómico
é maior nos seres procarióticos e menor nos eucarióticos. Na base da redução da
entropia estão as regularidades que perfazem as regiões repetitivas do ADN. As regiões
repetitivas compõem-se sobretudo de padrões aproximados, que incluem pontualmente
mutações, delecções, inserções ou gaps. Os padrões exactos são menos relevantes e
geralmente apresentam-se em numerosas repetições adjacentes. A redundância do ADN
também tem manifestações estatísticas e probabilísticas. As redundâncias das
sequências de ADN são a fonte de recursos de compressão, as grandes repetições
indicam-se para a compressão substitucional com recurso a dicionário, enquanto que as
evidências estatísticas e probabilísticas permitem modelar e predizer parcialmente a
sucessão de símbolos (bases), utilizando compressores estatísticos para capitalizar esse
potencial de compressão. Considerando a entropia máxima para o ADN, a sua
codificação corresponde a 2 bits por base. Em média, os melhores compressores
disponíveis, concebidos para a especificidade do ADN, alcançam os 1,7 bits/base, o que
corresponde a uma taxa de compressão de apenas 15%, valor que é demonstrativo da
dificuldade inerente.
O trabalho realizado corresponde a um framework de análise e compressão de
sequências de ADN, cuja aplicação principal corresponde ao DNALight. O DNALight é
uma solução híbrida para compressão de informação genómica baseada na cooperação
de várias metodologias vocacionadas para absorver ocorrências das diferentes tipologias
de redundâncias presentes nas cadeias de nucleótidos. De facto, a compressão não é
possível sem análise. É na completa análise que reside a obtenção dos recursos que
permitirão reduzir a entropia. Para a análise de sequências de ADN desenvolveram-se
algoritmos inovadores para a pesquisa de padrões exactos (GRASPm) e aproximados
v
(SimSearch) que alcançam desempenhos que superam destacadamente o estado da arte.
Estes algoritmos intervêm na primeira fase do DNALight que aproveita o potencial dos
padrões mais representativos para a compressão substitucional baseada em dicionário de
padrões exactos e aproximados. Para maximizar as captações de padrões, a pesquisa é
exaustiva e efectuada multi-nível, ou seja, na sequência normal 5’-3’, na complementar
natural 3’-5’, e também nas duas restantes complementares artificiais. Na segunda fase
do DNALight, que procura fazer o aproveitamento das redundâncias desconsideradas
pela captação da primeira fase, são construídos modelos probabilísticos de linguagem
compactos com bases nas regiões menos repetitivas que transitam para esta fase, e que
constituem o input para esta metodologia complementar. Em concorrência, os modelos
geram predições sustentadas nas apreciações probabilísticas de modelos de linguagem
globais e locais. As predições acertadas ou aproximadas permitem codificações mais
económicas pois criam maior desequilíbrio no modelo probabilístico de codificação,
beneficiando o desempenho da codificação aritmética que encerra o processo. O
processo de descompressão é similar mas reverso ao descrito para a compressão. Os
resultados experimentais colocam o DNALight como novo integrante do estado da arte
em compressão de sequências de ADN, superando consistentemente, mas em pequena
escala, os seus antecessores.
