Maximum likelihood of evolutionary trees: hardness and approximation | Zendy

Benny Chor | Zendy; Tamir Tuller | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Maximum likelihood of evolutionary trees: hardness and approximation

Author(s) -

Benny Chor,

Tamir Tuller

Publication year - 2005

Publication title -

bioinformatics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 3.599

H-Index - 390

eISSN - 1367-4811

pISSN - 1367-4803

DOI - 10.1093/bioinformatics/bti1027

Subject(s) - multiplicative function , logarithm , tree (set theory) , mathematics , computational complexity theory , maximum likelihood , approximation algorithm , maximum parsimony , algorithm , computer science , combinatorics , phylogenetic tree , statistics , mathematical analysis , clade , biochemistry , chemistry , gene

Maximum likelihood (ML) is an increasingly popular optimality criterion for selecting evolutionary trees. Yet the computational complexity of ML was open for over 20 years, and only recently resolved by the authors for the Jukes-Cantor model of substitution and its generalizations. It was proved that reconstructing the ML tree is computationally intractable (NP-hard). In this work we explore three directions, which extend that result.

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