Orientador: Fernando José Von ZubenTese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de ComputaçãoResumo: A biclusterização provou ser uma poderosa técnica de análise de dados devido ao seu amplo sucesso em vários domínios de aplicação. No entanto, a literatura existente apresenta soluções eficientes apenas para enumerar biclusters maximais com valores constantes, ou abordagens baseadas em heurísticas que não podem encontrar todos os biclusters ou nem mesmo garantir a maximalidade dos biclusters obtidos. Nesta tese, nós apresentamos uma família genérica de algoritmos de biclusterização para enumerar todos os biclusters maximais com (i) valores constantes nas linhas, (ii) valores constantes nas colunas, ou (iii) valores coerentes. Fornecemos versões para biclusters perfeitos e perturbados. Nossos algoritmos têm quatro propriedades-chave (apenas o algoritmo para biclusters perturbados com valores coerentes não possui a primeira propriedade): eles são (1) eficientes (têm tempo polinomial por bicluster), (2) completos (encontram todos os biclusters maximais), (3) corretos (todos os biclusters atendem a medida de similaridade definida pelo usuário), e (4) não-redundantes (todos os biclusters obtidos são maximais e o mesmo bicluster não é enumerado mais de uma vez). Os algoritmos propostos são baseados em uma generalização de um eficiente algoritmo de análise de conceitos formais, chamado In-Close2. Os resultados experimentais apontam para a necessidade de termos algoritmos enumerativos de biclusterização eficientes, e nos fornecem informações valiosas sobre a escalabilidade de nossa família de algoritmos, como também de sua sensibilidade aos parâmetros definidos pelo usuário. Nossos algoritmos foram aplicados com sucesso em dois problemas do mundo real: (i) a análise de enriquecimento de ontologias gênicas, e (ii) a análise e identificação de biomarcadores. Na primeira aplicação, mostramos como algoritmos pseudo enumerativos de biclusterização (que não possuem pelo menos uma das três últimas propriedades-chave) falham em encontrar todos os biclusters enriquecidos, bem como todos os genes que pertencem a esses biclusters. Na segunda aplicação, mostramos a utilidade de nossos algoritmos para testar a capacidade discriminatória de biomarcadores propostos na literatura, bem como para propor biomarcadores a partir do zero. Apresentamos também uma maneira de extrair regras de classificação associativas dos nossos biclusters, apontando para a possibilidade de construção de classificadores com base em nossas soluçõesAbstract: Biclustering has proved to be a powerful data analysis technique due to its wide success in various application domains. However, the existing literature presents efficient solutions only for enumerating maximal biclusters with constant values, or heuristic-based approaches which cannot find all biclusters or even ensure the maximality of the obtained biclusters. Here, we present a general family of biclustering algorithms for enumerating all maximal biclusters with (i) constant values on rows, (ii) constant values on columns, or (iii) coherent values. Versions for perfect and for perturbed biclusters are provided. Our algorithms have four key properties (only the algorithm for perturbed biclusters with coherent values fails to exhibit the first property): they are (1) efficient (take polynomial time per pattern), (2) complete (find all maximal biclusters), (3) correct (all biclusters attend the user-defined measure of similarity), and (4) non-redundant (all the obtained biclusters are maximal and the same bicluster is not enumerated twice). They are based on a generalization of an efficient formal concept analysis algorithm called In-Close2. Experimental results point to the necessity of having efficient enumerative biclustering algorithms and provide a valuable insight into the scalability of our family of algorithms and its sensitivity to user-defined parameters. Our algorithms were successfully applied in two real-world problems: (i) the gene ontology enrichment analysis, and (ii) the analysis and identification of biomarkers. In the first application, we show how pseudo enumerative biclustering algorithms (that miss at least one of the three last key properties) fail in finding all enriched biclusters and all genes that belong to these biclusters. In the second application, we show the usefulness of our algorithms in testing the discriminatory capability of proposed biomarkers, and in proposing biomarkers from scratch. We also present a way of extracting associative classification rules from our biclusters, guiding to the possibility of building classifiers based on our solutionsDoutoradoEngenharia de ComputaçãoDoutora em Engenharia ElétricaCAPES