Departamento de Eletr´onica, Universidade de Aveiro Telecomunicac¸˜oes e Inform´atica 2015 Programa de Doutoramento em Inform´atica das Universidades de Aveiro, Minho e Porto Lu´ıs Miguel de Algoritmos de compress˜ao sem perdas para imagens Oliveira Matos de microarrays e alinhamento de genomas completos Lossless compression algorithms for microarray images and whole genome alignments Departamento de Eletr´onica, Universidade de Aveiro Telecomunicac¸˜oes e Inform´atica 2015 Programa de Doutoramento em Inform´atica das Universidades de Aveiro, Minho e Porto Lu´ıs Miguel de Algoritmos de compress˜ao sem perdas para imagens Oliveira Matos de microarrays e alinhamento de genomas completos Lossless compression algorithms for microarray images and whole genome alignments Tese apresentada `as Universidades de Aveiro, Minho e Porto para cumpri- mento dos requisitos necess´arios `a obtenc¸˜ao do grau de Doutor em In- form´atica, realizada sob a orienta¸c˜ao cient´ıfica do Doutor Ant´onio Jos´e Ribeiro Neves, Professor Auxiliar do Departamento de Eletr´onica, Teleco- munica¸c˜oes e Inform´atica da Universidade de Aveiro, e do Doutor Armando Jos´e Formoso de Pinho, Professor Associado com Agregac¸˜ao do Departa- mento de Eletr´onica, Telecomunica¸c˜oes e Inform´atica da Universidade de Aveiro. Trabalho financiado pelas seguintes entidades: (cid:367)(cid:381)(cid:336)(cid:381)(cid:415)(cid:393)(cid:381) - versão vertical CORES universidade uni>ACv o VmmAae RrdceIaAs NcfrorTiit EpisvSeo n DdsiAaa d dsMaigA plaRa,a rCsaAe smed rd uetsicliezriatidvao ,d cdeo vma raeiasdsians a ftoaurrma aevs c.omeo síimrboloo. de aveiro universidade de aveiro POSITIVO / CINZA UNIÃO EUROPEIA GOVERPONORT DUAG RUEEPSÚABLICA Fundo Social Europeu theoria poiesis praxis universidade de aveiro 30 anos a projectar futuros NEGATIVO theoria poiesis praxis universidade de aveiro 30 anos a projectar futuros (cid:75)(cid:3)(cid:62)(cid:381)(cid:336)(cid:381)(cid:415)(cid:393)(cid:381)(cid:3)(cid:282)(cid:258)(cid:3)(cid:38)(cid:18)(cid:100)(cid:3)(cid:296)(cid:381)(cid:349)(cid:3)(cid:393)(cid:396)(cid:286)(cid:448)(cid:349)(cid:400)(cid:410)(cid:381)(cid:3)(cid:286)(cid:373)(cid:3)(cid:282)(cid:437)(cid:258)(cid:400)(cid:3) | das e não permitidas vvmmaaaarrirriaccaçaaçõ õcceeoossmm p d allooaragg m oouttatiiipplriczooaa àeç mãeos 2qe umline hrsdaitasu ançuõmeas leinshpaeciais: 02/03 ú(cid:28)(cid:448)(cid:258)(cid:373)n(cid:396)i(cid:349)c(cid:3)(cid:258)(cid:410)a(cid:286)(cid:374)s(cid:396)(cid:410) (cid:373)v(cid:286)e(cid:3)(cid:381)(cid:288)r(cid:400)(cid:3)s(cid:393)(cid:3)õ(cid:282)(cid:381)e(cid:286)(cid:400)s(cid:3)(cid:400).(cid:282)(cid:351)(cid:448)(cid:349)(cid:400)(cid:286)(cid:393)(cid:367)(cid:856)(cid:381)(cid:400)(cid:349)(cid:277)(cid:262)(cid:381)(cid:3)(cid:374)(cid:286)(cid:374)(cid:346)(cid:437)(cid:373)(cid:258)(cid:3)(cid:381)(cid:437)(cid:410)(cid:396)(cid:258)(cid:3) devi marca e logotipo em linha para aplicações de redução limite [aplicações em lápis, canetas, etc] |a utilizações in marca para aplicação em estacionário [papel de carta, envelope, fax, etc] c ar m a d s e õ ç a ari v | uunniivveerrssiiddaaddee ddee aavveeiirroo 3300 aannooss aa pprroojjeeccttaarr ffuuttuurrooss uunniivveerrssiiddaaddee ddee aavveeiirroo 3300 aannooss aa pprroojjeeccttaarr ffuuttuurrooss uunniivveerrssiiddaaddee ddee aavveeiirroo 3300 aannooss aa pprroojjeeccttaarr ffuuttuurrooss uunniivveerrssiiddaaddee ddee aavveeiirroo 3300 aannooss aa pprroojjeeccttaarr ffuuttuurrooss uunniivveerrssiiddaaddee ddee aavveeiirroo 3300 aannooss aa pprroojjeeccttaarr ffuuttuurrooss uunniivveerrssiiddaaddee ddee aavveeiirroo 3300 aannooss aa pprroojjeeccttaarr ffuuttuurrooss uunniivveerrssiiddaaddee ddee aavveeiirroo 3300 aannooss aa pprroojjeeccttaarr ffuuttuurrooss uunniivveerrssiiddaaddee ddee aavveeiirroo 3300 aannooss aa pprroojjeeccttaarr ffuuttuurrooss uunniivveerrssiiddaaddee ddee aavveeiirroo 3300 aannooss aa pprroojjeeccttaarr ffuuttuurrooss alguns exemplos de utilizações indevidas a utilização da logomarca não suporta distorções, alteração de posição relativa dos elementos, mudanças de tipografia ou qualquer outras configurações para além das previstas pelo autor. o ju´ri / the jury presidente / president Doutor Jo˜ao Carlos Matias Celestino Gomes da Rocha Professor Catedr´atico da Universidade de Aveiro vogais / examiners committee Doutor Paulo Jorge dos Santos Gonc¸alves Ferreira Professor Catedr´atico da Universidade de Aveiro Doutor Jo˜ao Miguel Raposo Sanches Professor Auxiliar com Agrega¸c˜ao da Universidade de Lisboa Doutor Lu´ıs Filipe Barbosa Almeida Alexandre Professor Associado com Agrega¸c˜ao da Universidade da Beira Interior Doutor Lu´ıs Manuel Dias Coelho Soares Barbosa Professor Associado da Escola de Engenharia da Universidade do Minho Doutor Ant´onio Jos´e Ribeiro Neves (Orientador) Professor Auxiliar da Universidade de Aveiro agradecimentos Primeiro que tudo, gostava de agradecer aos meus orientadores, Professor Ant´onio Neves e Professor Armando Pinho pela oportunidade, orientac¸˜ao e todo o apoio dado durante o meu doutoramento. Foi gra¸cas `a experiˆencia, recomenda¸c˜oes e paciˆencia deles que foi poss´ıvel concluir este trabalho de investiga¸c˜ao. Tamb´em gostava de agradecer ao Professor Jos´e Moreira pela oportunidade e apoio dado num trabalho de investiga¸c˜ao paralelo, no primeiro ano do meu doutoramento. A todos os meus colegas do IEETA, principalmente ao Diogo Pratas, M´ario Rodrigues, David Campos, Lu´ıs Ribeiro e Marco Pereira, por todo o apoio e conselhos dados nos u´ltimos anos. Quero tamb´em agradecer `a Universidade de Aveiro, especialmente ao IEETA e ao DETI, por me providenciar as condi¸c˜oes necess´arias para executar este trabalho. Agrade¸co tamb´em todo o apoio financeiro prestado nas mais diversas ocasi˜oes. Por u´ltimo, um agradecimento especial `a minha fam´ılia, aos meus pais Armindo e Margarida e ao meu irm˜ao Gabriel, pelo seu apoio genu´ıno e ilimitado durante este per´ıodo. acknowledgements First, I would like to thank my supervisors, Professor Ant´onio Neves and Professor Armando Pinho for the opportunity, guidance and all the support giventhroughthePh.D.Itwasthankstotheirexperience,recommendations and patience, that it was possible to conclude this research work. I also would like to thank Professor Jos´e Moreira for the opportunity and the support given in a parallel research work, in the first year of my Ph.D. To all my IEETA colleagues, mainly Diogo Pratas, M´ario Rodrigues, David Campos,Lu´ısRibeiroandMarcoPereira,forallthesupportandadvicegiven through the last years. I also want to thank University of Aveiro, specially IEETA and DETI, for providing the necessary conditions to execute this work. I also thank to all financial support provided in several occasions. Finally, a special thanks to my family, my parents Armindo and Margarida and my brother Gabriel for their genuine and unlimited support during this period. Palavras-chave Compress˜ao de imagem sem perdas, imagens de microarrays, modelos de contexto-finito, decomposi¸c˜ao em arvore bin´aria, decomposi¸c˜ao em planos bin´arios, redu¸c˜ao de planos bin´arios, alinhamento de genomas completos, formato de multi-alinhamento. Resumo Hoje em dia, no s´eculo XXI, a expans˜ao intermin´avel de informa¸c˜ao ´e uma grande preocupa¸c˜ao mundial. O ritmo ao qual os recursos de ar- mazenamento e comunica¸c˜ao est˜ao a evoluir n˜ao ´e suficientemente r´apido para compensar esta tendˆencia. De forma a ultrapassar esta situa¸c˜ao, s˜ao necess´arias ferramentas de compress˜ao sofisticadas e eficientes. A com- press˜ao consiste em representar informac¸˜ao utilizando a menor quantidade de bits poss´ıvel. Existem dois tipos de compress˜ao, com e sem perdas. Na compress˜ao sem perdas, a perda de informac¸˜ao n˜ao ´e tolerada, por isso a informa¸c˜ao descodificada ´e exatamente a mesma que a informa¸c˜ao que foi codificada. Por outro lado, na compress˜ao com perdas alguma perda ´e aceit´avel. Neste trabalho, foc´amo-nos apenas em m´etodos de compress˜ao sem perdas. O objetivo desta tese consistiu na criac¸˜ao de ferramentas de compress˜ao sem perdas para dois tipos de dados. O primeiro tipo de da- dos ´e conhecido na literatura como imagens de microarrays. Estas imagens tˆem 16 bits por p´ıxel e uma resolu¸c˜ao espacial elevada. O outro tipo de dados´e geralmente denominado como alinhamento de genomas completos, particularmenteaplicadoaficheirosMAF. Relativamente`asimagensdemi- croarrays, melhor´amosalgunsm´etodosdecompress˜aoespec´ıficosutilizando algumas t´ecnicas de pr´e-processamento (segmenta¸c˜ao e redu¸c˜ao de planos bin´arios). Al´em disso, desenvolvemos tamb´em um m´etodo de compress˜ao baseado em estimac¸˜ao dos valores dos p´ıxeis e em misturas de modelos de contexto-finito. Foi tamb´em considerada, uma abordagem baseada em decomposic¸˜ao em ´arvore bin´aria. Foram desenvolvidas duas ferramentas de compress˜ao para ficheiros MAF. A primeira ferramenta, ´e baseada numa mistura de modelos de contexto-finito e codificac¸˜ao aritm´etica, onde ape- nas as bases de ADN e os s´ımbolos de alinhamento foram considerados. A segunda, designada como MAFCO, ´e uma ferramenta de compress˜ao completa que consegue lidar com todo o tipo de informac¸˜ao que pode ser encontrada nos ficheiros MAF. MAFCO baseia-se em v´arios modelos de contexto-finito e permite compress˜ao/descompress˜ao paralela de ficheiros MAF.