Distância de Transposição Através da Transformação em Permutação Simples

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 implementamos uma estrutura de dados proposta por Feng e Zhu, chamada Permutation Tree, que melhora o tempo e complexidade de execução para se 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√log n). Implementaremos o algoritmo com complexidade de tempo O(n log n), utilizando a estrutura Permutation Tree.