On (k.l)-leaf powers

23 mins 48 secs, 140.43 MB, Flash Video 480x360, 25.0 fps, 44100 Hz, 805.61 kbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/502/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

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

Wagner, P

Language:

eng (English)

Distribution:

World

(downloadable)

Credits:

Author:

Wagner, P

Explicit content:

Aspect Ratio:

4:3

Screencast:

Bumper:

UCS Default

Trailer:

UCS Default


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.

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)

Streaming Media Service Upload

On (k.l)-leaf powers