Evènement pour le groupe BioInformatique et Visualisation


Date 2012-12-06  11:00-12:30
Titre LCA Skeleton Tree in Linear Time 
RésuméFischer and Huson introduced in 2010 the notion of LCA skeleton tree: the restriction of a tree to a given subset of the nodes, and they gave an algorithm for computing the LCA skeleton tree of a subset of $m$ nodes in a tree with $n$ nodes in $O(mlog{n}/loglog{n})$ time after $O(n)$ time preprocessing, based on the fact that the LCA of any two nodes in a tree with $n$ nodes can be determined in $O(1)$ time after $O(n)$ time preprocessing. In this talk, we present a simple algorithm for computing the LCA skeleton tree of a subset of $m$ nodes in a tree with $n$ nodes in $O(m)$ time, after $O(n)$ time preprocessing. The LCA skeleton tree of a taxonomic tree has applications in the taxonomic assignment of sequence reads in metagenomics. 
Lieu178 
OrateurGabriel Valiente 
Emailmacha@labri.fr 



Aucun document lié à cet événement.

Retour
Retour à l'index