Title: Parallelisation of a multi-neighbourhood local search heuristic for a phylogeny problem

Authors: G.V.R. Viana, F.A.C. Gomes, C.E. Ferreira, C.N. Meneses

Addresses: Universidade Federal do Ceara, Centro de Ciencias, Departamento de Computacao, Bloco 910, Campus do Pici, 60455-760, Fortaleza, CE, Brasil. ' Universidade Federal do Ceara, Centro de Ciencias, Departamento de Computacao, Bloco 910, Campus do Pici, 60455-760, Fortaleza, CE, Brasil. ' Universidade de Sao Paulo, Instituto de Matematica e Estatistica, Departamento de Ciencia da Computacao, Rua do Matao 1010, Cidade Universitaria, 05508-090, Sao Paulo, SP, Brasil. ' Universidade Federal de Goias, Instituto de Informatica, Bloco IMF I, sala 239, Campus II, Samambaia, Caixa Postal 131, 74001-970, Goiania, Go, Brasil

Abstract: In this work we study a phylogeny problem. That is, given a collection of organisms, we want to reconstruct the evolutionary history of the organisms. We are interested in inferring relationships between the organisms. For a number of reasonable biological hypotheses the problem becomes NP-hard. Besides that, the problem data is large enough to inhibit anyone using exact algorithms to solve, in practical computational time, real instances of the problem. In this work, we propose an innovative technique based on local search procedures that use multiple starts and diversified neighbourhoods.

Keywords: computational biology; phylogeny; heuristics; parallel programming; bioinformatics; organisms; evolutionary history; inferring relationships; local search; multiple starts; diversified neighbourhoods.

DOI: 10.1504/IJBRA.2009.024034

International Journal of Bioinformatics Research and Applications, 2009 Vol.5 No.2, pp.163 - 177

Published online: 24 Mar 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article