Who is Who in Phylogenetic Networks

Publication no #684   Type :   Html | Bib | Both

Created: 2009-02-08 00:10:33     Modified: 2010-04-30 17:38:41

684 Johannes Fischer and Daniel H. Huson. New Common Ancestor Problems in Trees and Directed Acyclic Graphs. In IPL, Vol. 110(8-9):331-335, 2010. Keywords: explicit network, phylogenetic network, polynomial. Note: http://www-ab.informatik.uni-tuebingen.de/people/fischer/lsa.pdf.         Toggle abstract "We derive a new generalization of lowest common ancestors (LCAs) in dags, called the lowest single common ancestor (LSCA). We show how to preprocess a static dag in linear time such that subsequent LSCA-queries can be answered in constant time. The size is linear in the number of nodes. We also consider a "fuzzy" variant of LSCA that allows to compute a node that is only an LSCA of a given percentage of the query nodes. The space and construction time of our scheme for fuzzy LSCAs is linear, whereas the query time has a sub-logarithmic slow-down. This "fuzzy" algorithm is also applicable to LCAs in trees, with the same complexities. © 2010 Elsevier B.V. All rights reserved."