Minimum Recombination Histories by Branch and Bound | Zendy

Rune B. Lyngsø | Zendy; Yun Song | Zendy; Jotun Hein | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Minimum Recombination Histories by Branch and Bound

Author(s) -

Rune B. Lyngsø,

Yun Song,

Jotun Hein

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-29008-7

DOI - 10.1007/11557067_20

Subject(s) - recombination , computer science , branch and bound , set (abstract data type) , genetic algorithm , upper and lower bounds , diversity (politics) , algorithm , mathematics , biology , genetics , gene , machine learning , sociology , anthropology , programming language , mathematical analysis

Recombination plays an important role in creating genetic diversity within species, and inferring past recombination events is central to many problems in genetics. Given a set M of sampled sequences, finding an evolutionary history for M with the minimum number of recombination events is a computationally very challenging problem. In this paper, we present a novel branch and bound algorithm for tackling that problem. Our method is shown to be far more efficient than the only preexisting exact method, described in [1]. Our software implementing the algorithm discussed in this paper is publicly available.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research