Consensus Algorithms for Trees and Strings

摘要: This thesis studies the computational complexity and polynomial-time approximability of a number discrete combinatorial optimization problems involving labeled trees strings. The considered have applications to molecular biology, pattern matching, many other areas computer science. is divided into three parts. In first part, we study some in which goal infer leaf-labeled tree from set constraints on lowest common ancestor relations. Our NP-hardness proofs, approximation algorithms, exact algorithms indicate that these become computationally easier if resulting required comply with prespecified left-to-right ordering leaves. second part deals two related identifying shared substructures trees. We investigate how maximum agreement subtree problem depends height input Then, show running time currently fastest known algorithm for alignment between ordered can be reduced instances are similar scoring scheme satisfies natural assumptions. third devoted radius diameter clustering binary strings where distances measured using Hamming metric. present new inapproximability results various types as well certain restrictions problems. (Less)