To access the full text documents, please follow this link:

Tabu search for the founder sequence reconstruction problem: a preliminary study
Roli, Andrea; Blum, Christian
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
The problem of inferring ancestral genetic information in terms of a set of founders of a given population arises in various biological contexts. In optimization terms, this problem can be formulated as a combinatorial string problem. The main problem of existing techniques, both exact and heuristic, is that their time complexity scales exponentially, which makes them impractical for solving large-scale instances. We developed a new constructive heuristic and a tabu search method with the explicit aim of providing solutions in a reduced amount of computation time. Experimental results show that when the number of founders grows, our algorithms have advantages over the ones proposed in the literature.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Intel·ligència artificial
Heuristic programming
Programació heurística

Show full item record

Related documents

Other documents of the same author

Blum, Christian; Puchinger, Jakob; Raidl, Günther; Roli, Andrea
Roli, Andrea; Benedettini, Stefano; Stützle, Thomas; Blum, Christian
Blum, Christian; Puchinger, Jakob; Raidl, Günther; Roli, Andrea
Hernández Pibernat, Hugo; Baumgartner, Tobias; Blesa Aguilera, Maria Josep; Blum, Christian; Kröller, Alexander; Fekete, Sandor P.