MDL hierarchical clustering for stemmatology

Po-Hsiang Lai, Teemu Teppo Roos, Joseph O'Sullivan

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review


In real life, one often encounters situations where one needs to infer a structural relationship among data points based on an incomplete dataset. Stemmatology and phylogenetics are two classes of such problems where partial text scripts or genome sequences are available and the goal is to reconstruct the copying history of scripts or evolutionary relations among species. In this paper, we study the potential applications of minimum description length (MDL) concepts to the structural inference problem, particularly focusing on stemmatology where in addition to missing data points, the available data points have missing values. We offer new insights on how to handle these issues, especially missing values. We develop a general algorithm based on MDL insights that is simple to implement and can be used along with other existing algorithms, and propose a generic MDL encoder with minimal assumptions made about the data. In simulations, our method performs reasonably well on a simple dataset and outperforms major existing methods in a larger and much more realistic dataset. We discuss directions and ongoing efforts to further improve performance.
Titel på gästpublikationInformation Theory Proceedings (ISIT)
RedaktörerM. Gastpar, R. Heath, K. Narayanan
Antal sidor5
FörlagIEEE Press
Utgivningsdatumjun 2010
ISBN (tryckt)978-1-4244-7890-3
ISBN (elektroniskt)978-1-4244-7891-0
StatusPublicerad - jun 2010
MoE-publikationstypA4 Artikel i en konferenspublikation
Evenemang2010 IEEE International Symposium on Information Theory - Austin, Texas, Förenta Staterna (USA)
Varaktighet: 13 jun 201018 jun 2010


  • 113 Data- och informationsvetenskap

Citera det här