Algoritmos para alinhamento de redes metabólicas

Abstract

O alinhamento de redes metab olicas e um t opico habitual no contexto da biologia computacional. Por ele podemos, por exemplo, aferir rela c~oes de evolu c~ao, parentesco ou funcionais entre esp ecies. O problema pode ser modelado nas mais variadas formas e trabalhado utilizando diferentes metodologias. Neste trabalho buscamos descrever uma vis~ao geral sobre o assunto, todavia, dedicando algumas p aginas ao estudo aprofundado de recentes trabalhos de relev^ancia sobre o tema a luz da teoria dos grafos. Inicialmente apresentamos de ni c~oes b asicas necess arias ao estudo do tema, da biologia a teoria da computa c~ao, seguidas pela exposi c~ao das modelagens mais comuns de redes metab olicas. Passamos ao alinhamento de sequ^encias, vias e redes metab olicas, sendo os dois ultimos o foco do trabalho, estudando detalhadamente alguns algoritmos. Apresentamos ainda uma s ntese acerca de trabalhos relacionados ao trabalho corrente.

The alignment of metabolic networks is an usual topic in the context of computational biology. Studying it we can, for example, measure evolutionary, lineage or functional relationships between species. The problem can be modeled in many ways and handled using di erent methodologies. In this work we want to achieve a survey about the subject, devoting a few pages to the study of recent work of relevance to the topic using graph theory. First we present basic de nitions necessary to the study of subject, from biology to theoretical computer science, followed by exposure of the most common ways of modeling metabolic networks. Then we discuss the alignment of sequences, pathways and metabolic networks, the last two being the focus of this work, studying some algorithms in detail. We also present an overview of related work.