Abstract
A matrix M is noisy-ultrametric if there exists a rooted tree T such that for all leaves i,j,k, Mij < min {Mik, Mjk} if and only if lcaT(i,j) below lcaT(i,k) = lcaT(j,k), where lcaT(i,j) denotes the lowest common ancestor of nodes i and j in a rooted tree T. In this thesis, given an n-by-n matrix M, we present an algorithm to recognize whether it is noisy-ultrametric or not. If yes, we construct the correspondent tree. The time complexity is O(n4).