Leibniz MMS Days 2017 - Abstract

Oswald, Marcus

Modeling decision tree training problems as a Mixed Integer Program (MIP) yields optimal decision trees

The problem of constructing an optimal binary decision tree is known to be NP-complete. Therefore most current implementations base on heuristics where local optimality criteria are used. Our approach optimizes decision trees globally by construction a suitable MIP. In recent years both very high computing power and very efficient branch-and-cut algorithms for solving MIPs make the running time more and more realistic for practical applications. We applied our method for the discrimination of tumor samples into distinct telomere maintenance mechanisms (TMM). Telomeres are at the end of the chromosomes and shorten after each replication serving as a crucial check point for protecting cells from unbound replication. Tumor cells circumvent this by either re-evoking the enzyme for elongation or redirecting DNA-repair mechanisms know as alternative TMM. Our approach allowed classifying the tumor samples with an accuracy of 0.95 when using the experimental gold standard (C-circle assays).