---

Biologia Computacional é uma área da Ciência da Computa‡Æo que tem por objetivo o estudo e aplica‡Æo de técnicas e ferramentas computacionais aos problemas da Biologia Molecular. Dentre os problemas pesquisados, encontra-se o de evolu‡Æo molecular, onde sÆo estudados métodos para comparar sequencias de espécies distintas, baseados em eventos mutacionais. Estes métodos geram medidas de distância, que podem ser empregadas para verificar o relacionamento em termos evolutivos entre dois organismos. Uma técnica de computar distância é comparar blocos, formados por um ou mais genes, de genomas de dois organismos. Neste trabalho propomus a implementa‡Æo da recente estrutura de dados de Feng e Zhu chamada de árvore de permuta‡Æo, que melhora o tempo de execu‡Æo para realizar transposi‡äes em uma permuta‡Æo. O algoritmo 1,5-aproximativo de Hartman e Shamir para ordena‡Æo de uma permuta‡Æo por transposi‡äes possui complexidade de tempo O(n3/2_logn). Utilizando a árvore de permuta‡Æo, implementamos o algoritmo com complexidade de tempo O(n log n).

---

Formado em Ciência da Computa‡Æo pela Universidade Federal de Juiz de Fora e com Mestrado em Engenharia de Sistemas pela COPPE. Trabalha com análise e desenvolvimento de softwares web e mobile. Experiência com programa‡Æo Java e NodeJS do lado do servidor e Google Android para desenvolvimento de aplicativos.

---