Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6876231 | Theoretical Computer Science | 2014 | 11 Pages |
Abstract
For p partitions and |M| possible substitution models, there are |M|p possible model assignments. Since the number of combinations grows exponentially with p, an exhaustive search for the highest scoring assignment is computationally prohibitive for |M|>1. We show that the problem of finding the optimal protein substitution model assignment under linked branch lengths on a given, tree topology, is NP-hard. Our results imply that one should employ heuristics to approximate the solution, instead of striving for the exact solution. Alternatively, the problem can be simplified by relaxing the assumptions.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kassian Kobert, Jörg Hauser, Alexandros Stamatakis,