Abstract
We reexamine the deferred path heuristic originally developed by Schwikowski and Vingron in the late 1990s. Given a set of sequences, e.g. DNA, this heuristic simultaneously finds a multiple alignment and a phylogenetic tree. We give a unified description of the heuristic where such intermediate constructs as fork alignment graphs are made obsolete. Based on this description an efficient implementation is straightforward. We discuss two improvements of which one is intended to provide better quality solutions and one is intended to provide a substantial speed-up. This is confirmed by experiments on several real-life problem instances.
Original language | English |
---|---|
Title of host publication | Proceedings Of CompBioNets05 |
Subtitle of host publication | Algorithms and Computional Methods for Biochemical and Evolutionary Networks |
Publisher | King's College Publications |
Pages | 75-92 |
Number of pages | 18 |
Publication status | Published - 2005 |
Event | Algorithms and Computional Methods for Biochemical and Evolutionary Networks - Lyon, France Duration: 5 Dec 2005 → 7 Dec 2005 Conference number: 2 |
Conference
Conference | Algorithms and Computional Methods for Biochemical and Evolutionary Networks |
---|---|
Country/Territory | France |
City | Lyon |
Period | 5/12/05 → 7/12/05 |
Keywords
- computional biology
- Evolutionary trees