Locality-sensitive hashing without false negatives for lp

Pacuk, Andrzej; Sankowski, Piotr; Wegrzycki, Karol; Wygocki, Piotr

We consider the problem of reconciling gene trees with a species tree based on the widely accepted Gene Duplication model$\backslash$n from Goodman et al. Current algorithms that solve this problem handle only binary gene trees or interpret polytomies in the gene tree as true.$\backslash$n While in practice polytomies occur frequently, they are typically not true. Most polytomies represent unresolved evolutionary$\backslash$n relationships. In this case a polytomy is called apparent. In this work we modify the problem of reconciling gene and species trees by interpreting polytomies to be apparent, based$\backslash$n on a natural extension of the Gene Duplication model. We further provide polynomial time algorithms to solve this modified$\backslash$n problem.

Research areas:

• Algorithmics
• Multiplex (3rd period)

Year:

2016

Type of Publication:

Article

Journal:

LNCS

Volume:

9797

Pages:

105-118

ISSN:

1432-0541

DOI:

10.1007/s00453-016-0176-1