Comparison of Random Trees and Hierarchical Structure of Chromatin Domains

The object of research of this work is the graphs - hierarchical trees, describing the domain structure of Hi-C chromatin maps. The purpose of the research is to develop an algorithm for quantitative comparison of such hierarchical trees. In this paper, a quantitative measure of proximity of two hierarchical trees (“distance”) was proposed, an algorithm was developed for its calculation, implemented in a console application in the C ++ programming language. A detailed statistical analysis of the proposed proximity measure was carried out for random trees of various sizes, correlated trees and trees obtained from each other by a given number of small elementary perturbations. The dependence of distances and their distributions on the parameters of the problem was analyzed, a number of hypotheses about the scaling behavior of the corresponding dependences were put forward. The results obtained in this work can serve as a basis for comparing the hierarchical trees obtained by analyzing experimental Hi-C maps