Um algoritmo de aproximação paralelo para transversal mínima com aplicação em análise da expressão gênica

Detalhes bibliográficos
Ano de defesa: 2002
Autor(a) principal: Ruchkys, Danielle Passos de
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://teses.usp.br/teses/disponiveis/45/45134/tde-20220712-120416/
Resumo: Com o recente progresso de tecnologias como dos DNA-microarrays, é possível medir os níveis de expressão de milhares de genes simultaneamente no mesmo experimento. Uma rede genética é um modelo que descreve como o nível de expressão de cada gene é afetado pelos níveis de expresão de outros genes da rede. Dados os resultados de um experimento com N genes e M medidas de tempo (MN), consideramos os problema de encontrar um subconjunto de genes (K genes, onde KN) que explica o nível de expressão de um dado gene alvo que desejamos estudar. Neste trabalho, nós apresentamos um algoritmo de aproximação seqüencial de complexidades de tempo O(KM2N). Temos que K=O(M2) e a complexidade de tempo apenas em termos de M e N é O(M4N). Para desenvolver o algoritmo paralelo, usamos o modelo CGM, com P processadores. O principal resultado é um algoritmo de aproximação paralelo que determina os K genes em tempo de computação local O(KM2N sobre P) (ou O(M4N sobre P)) mais O(K) (ou O(M2)) rodadas de comunicação, utilizando espaço local O(M2N sobre P). Neste trabalho, também mostramos os tempos de execução obtidos pelos programas que implementam os algoritmos paralelo e seqüencial, utilizando uma máquina do tipo Beowulf, tendo como entrada matrizes de expressões geradas aleatoriamente. Também mostramos as acelerações obtidas pelo programa paralelo