Branch and bound construction of balanced minimum evolution optimal trees
Duration: 19 mins 3 secs
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Pardi, F (EMBL)
Tuesday 04 September 2007, 15:30-15:50 PLGw01 - Current Challenges and Problems in Phylogenetics |
|---|
| Created: | 2007-09-13 15:44 | ||
|---|---|---|---|
| Collection: | Phylogenetics | ||
| Publisher: | Isaac Newton Institute | ||
| Copyright: | Pardi, F | ||
| Language: | eng (English) | ||
| Distribution: |
World
(downloadable)
|
||
| Credits: |
|
||
| Explicit content: | No | ||
| Aspect Ratio: | 4:3 | ||
| Screencast: | No | ||
| Bumper: | /sms-ingest/static/new-4x3-bumper.dv | ||
| Trailer: | /sms-ingest/static/new-4x3-trailer.dv | ||
| Abstract: | The Balanced Minimum Evolution (BME) score has been recently proposed as a criterion for reconstructing phylogenetic trees based on a distance matrix. It is based on Pauplin's formula, which provides a natural estimate of the total length of a tree, based on its topology and a matrix of estimated pairwise distances. The objective is to find the tree topology that minimizes this length estimate, as short trees are usually the ones that best reflect the data.
Recently, it has been shown that Neighbor Joining can be viewed as a greedy algorithm trying to minimise BME. Together with other theoretical reasons, there are strong experimental reasons supporting BME-guided tree reconstruction. However, the published methods are heuristic and do not attempt to construct BME-optimal trees. The main aim of this talk will be to present a Branch and Bound approach for finding BME-optimal trees. We derived a simple bound on the BME score of a tree based on the score of a partially constructed tree. This allows us to eliminate the need to explore large parts of the space of all possible trees, but still guarantees that all optimal trees will be found. The efficiency of this approach compares well with that of other Branch and Bound approaches such as the ones for Maximum Parsimony. Finally the topological accuracy of the reconstructed trees will also be discussed. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 480x360 | 1.84 Mbits/sec | 263.54 MB | View | Download | |
| WebM | 480x360 | 512.1 kbits/sec | 71.52 MB | View | Download | |
| Flash Video | 480x360 | 806.05 kbits/sec | 113.06 MB | View | Download | |
| iPod Video | 480x360 | 505.51 kbits/sec | 70.90 MB | View | Download | |
| QuickTime | 384x288 | 848.0 kbits/sec | 118.94 MB | View | Download | |
| MP3 | 44100 Hz | 125.08 kbits/sec | 17.33 MB | Listen | Download | |
| Windows Media Video | 476.37 kbits/sec | 66.82 MB | View | Download | ||
| Auto * | (Allows browser to choose a format it supports) | |||||