Heuristics. (c2006)

LAUR Repository

Show simple item record

dc.contributor.author Kallab, Chadi
dc.date.accessioned 2011-10-27T07:39:21Z
dc.date.available 2011-10-27T07:39:21Z
dc.date.copyright 2006 en_US
dc.date.issued 2011-10-27
dc.date.submitted 2006-06-16
dc.identifier.uri http://hdl.handle.net/10725/925
dc.description Includes bibliographical references (l. 70). en_US
dc.description.abstract This thesis focuses on the NP-Hard problem of finding an optimal tree topology where leaves represent biological sequences. The problem consists of minimizing the number of changes between given and/or derived sequences. As the number of sequences to be compared increases, the size of the search space grows exponentially, requesting the use of optimization methods, to come up with an acceptable optimal topology. Even though, research is relating a large number of species and gene families to each others, the computation intensive load of many popular methods for evaluating trees (ex: parsimony and maximum likelihood) establish the quasi-inexistence of an exact solution for more than about 20 sequences. The alignment of two sequences (pairwise alignment), or multiple sequences (Multiple Sequence Alignment - MSA), and the alignment of short or long sequences such as an entire genome may require different types of algorithms. The algorithms used in all of these four cases are dynamic programming, linear programming based or heuristic-based or a combination of them. For large numbers of sequences to be aligned, heuristic methods may give a result similar to the exact solution offered by the dynamic programming or linear programming based algorithms, but in much shorter time. Heuristics used in phylogenetic inference include greedy algorithms, hill climbing, simulated annealing, and genetic algorithms. Thus, this research aims to suggest a general way to encode the problem into instances of different heuristic algorithms. Another focus of the document would be to suggest that the heuristics used, be implemented in a most optimal way, trying to get a compromise between speedup, flexibility and detailed tracing/chronology of each run of the algorithms. en_US
dc.language.iso en en_US
dc.subject Heuristic programming en_US
dc.subject Combinatorial optimization en_US
dc.title Heuristics. (c2006) en_US
dc.type Thesis en_US
dc.title.subtitle Encoding for parsimony phylogenetic trees & generic implementations en_US
dc.term.submitted Spring en_US
dc.author.degree MS in Computer Science en_US
dc.author.school Arts and Sciences en_US
dc.author.idnumber 199730860 en_US
dc.author.commembers Mr. Joe Khalife
dc.author.commembers Dr. Jean Takchi
dc.author.woa OA en_US
dc.description.physdesc 1 bound copy: vii, 70 leaves; ill., tables; 30 cm. available at RNL. en_US
dc.author.division Computer Science en_US
dc.author.advisor Dr. Haidar Harmanani
dc.identifier.doi https://doi.org/10.26756/th.2006.54 en_US
dc.publisher.institution Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account