On (k.l)-leaf powers
Duration: 23 mins 42 secs
Share this media item:
Embed this media item:
Embed this media item:
About this item
Description: |
Wagner, P (Rostock)
Tuesday 18 December 2007, 15:30-15:50 PLGw03 - Future Directions in Phylogenetic Methods and Models |
---|
Created: | 2008-01-11 17:23 | ||
---|---|---|---|
Collection: | Phylogenetics | ||
Publisher: | Isaac Newton Institute | ||
Copyright: | Wagner, P | ||
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: | We say that, for k>1 and l>k, a tree T is a (k,l)-leaf root of a graph G=(V,E), if V is the set of leaves of T, for all edges xy in E, the distance d(x,y) between x and y in T (i.e., the number of edges of the unique path between the leaves x and y in T) is at most k and, for all non-edges xy outside E, d(x,y) is at least l. A graph G is a (k,l)-leaf power, if it has a (k,l)-leaf root.
This new notion generalises the concept of k-leaf power, which was introduced and studied by Nishimura, Ragde and Thilikos in 2002, motivated by the search for underlying phylogenetic trees: "...a fundamental problem in computational biology is the reconstruction of the phylogeny, or evolutionary history, of a set of species or genes, typically represented as a phylogenetic tree..." The species occur as leaves of the phylogenetic tree. Recently, a lot of work has been done on k-leaf powers and roots as well as on their variants phylogenetic roots and Steiner roots. For k=3 and k=4, structural characterisations and linear time recognition algorithms of k-leaf powers are known, and, recently, a polynomial time recognition of 5-leaf powers was given. For larger k, the recognition problem is open. We give structural characterisations of (k,l)-leaf powers, for some k and l, which also imply efficient recognition of these classes, and in this way we also improve and extend a recent paper from 2006 by Kennedy, Lin and Yan on strictly chordal graphs and leaf powers. |
---|
Available Formats
Format | Quality | Bitrate | Size | |||
---|---|---|---|---|---|---|
MPEG-4 Video | 480x360 | 1.84 Mbits/sec | 327.90 MB | View | Download | |
WebM | 480x360 | 557.19 kbits/sec | 96.79 MB | View | Download | |
Flash Video | 480x360 | 805.61 kbits/sec | 140.43 MB | View | Download | |
iPod Video | 480x360 | 505.28 kbits/sec | 88.08 MB | View | Download | |
QuickTime | 384x288 | 848.17 kbits/sec | 147.85 MB | View | Download | |
MP3 | 44100 Hz | 125.03 kbits/sec | 21.58 MB | Listen | Download | |
Windows Media Video | 477.61 kbits/sec | 83.26 MB | View | Download | ||
Auto * | (Allows browser to choose a format it supports) |