Distance between trees

[Ablertus]

A teper sovsem netrivialnyj vopros: kto nibud znaet metod sravnenia derevyev? Prichem derevya ne binarnye, a s proizvolnym kolichestvom vetvey u uzla. Pod sravneniem imeetsa vvidu ne prosto proverka na odinakovost, a izmerenie distancii, tak chtoby potom sgenerirovat phylogeneticheskoe derevo. Budu vesma blagodaren za otvet.

[nm]

а ты $дистанцию определи, а потом подумаем

[Ablertus]

OK, popytayus popodrobnee:

1. Trees are lebelled, rooted, n-degree.

2. They're not ordered, but I think the branches of each node may be ordered according to any law (e. g. alphabetically)

3. Physically the leaves are species (substances) or reactions in a biochemical pathway. They may be treated as symbols of an alphabet, but the alphabet is endless (as anything in the nature). Hence, I can't use a predefined distance matrix, I have to develop a function for counting distance. The simplest law is the following: 0 for match, 1 for mismatch, deletion or insertion. The more sophisticated functions take into account the similarity degree between mismatching nodes. Actually, any distance-calculating rule may be used, as soon as you have an algorithm to compare the whole trees

P. S. Now I've got an idea, but I would like to address the community at first, to find out if anything suitable exists already. Discovering America is an unthankful job But all I've found so far is for binary trees.

[nm]

так, давай тогда разбираться.

пусть мы сравниваем узлы дерева (FOO и BAR)

1. если $FOO и $BAR содержат только листья и мы их сравниваем - то дистанция равна дистанции Левинштейна(число операций insert/delete).

2. думаем - если $FOO в данной позиции [1,n] имeeт поддерево , а $BAR - нет, то как мы считаем дистанцию? можно посчитать ее как num_elements($FOO[i]) -- в случаем если требовать, чтоб поддеревья всегда находились в нужной позиции узлов, которые мы сравниваем, а можно посчитать по-другому, постараться найти такое поддерево $BAR, которое совпадает с поддеревом $FOO и найти количество операций insert/delete для того, чтоб его привести в нужную позицию.
вобщем вот тут по-моему и проблема. после того, как ты точно определишь, что ты считаешь дситанцией между поддеревьями - реализация станет простой и ясной.

примеры:

[nm]

если я все правильно посчитал , то просто для узлов только с листьями:

FOO = [ a, b, c ], BAR = [ ] -> distance = 3
FOO = [ a, b, c ], BAR = [ a, a, b, c ] -> distance = 1
FOO = [ a, b, c ], BAR = [ b, c, a ] -> distance = 2 (убираем один силвол в начале, добавляем один в конце)


FOO = [ [a], [b], [c] ], BAR = [ а, [b], [c] ] ->
вариант 1 - distance = 2 (убираем дерево [a], добавляем символ)
вариант 2 - distance = 3 (убираем символ из под-дерева [a], убираем пустов поддерево, добавляем символ)

FOO = [ [a], [b], [c] ], BAR = [ [b], [c], [a] ] ->

вариант 1 - distance = 2 (убираем под-дерево [a], добавляем под-дерево [a] в конце)
вариант 2 - distance = 4 (убираем символ из под-дерева [a], убираем пустов поддерево,
добавляем пустое под-дерево, добавляем символ а)

мне лично по душе вариант 2 -
при подсчете дистанции между поддеревьям - разрешены только операции
удалить символ, добавить символ и удалить пустое дерево, вставить пустое дерево.

не обосновывая - такой набор операций кажется мне более простым в реализации и более логичным

[Agregat]

1. Возможно ли нарушение иерархии? Например у узла X два сына, а у каждого из них по три. Теперь в другом дереве у узла X сразу 6, во всем остальном деревья одинаковы - теперь насколько они похожи? Например, в случае биологии не знаю, для сравнения схем - они одинаковы.
2. Глобально, если возможны так же ротации - то NP полная задача.

[Ablertus]

Спасибо, nm и Виктор! Я честно говоря и не ожидал получить столь подробные ответы Тогда подумаем дальше?

>Возможно ли нарушение иерархии? Например у узла X два сына, а у каждого из них по три. Теперь в другом дереве у узла X сразу 6, во всем остальном деревья одинаковы - теперь насколько они похожи? Например, в случае биологии не знаю, для сравнения схем - они одинаковы.

Вообще то теоритечески возможны, хотя стоит проверить, могут ли такие пары деревьев в принципе возникнуть в моем случае (их структура не случайна, а в свою очередь основана на алгоритме).

>Глобально, если возможны так же ротации - то NP полная задача.

Если я правильно понял вопрос:

((a, b), (c, d)) и ((d, c), (b, a)) - идентичны.Играет роль лишь иерархия, а не последовательность детей у одного узла (tree is unordered). я тоже читал, что проблема в данном случае NP-complete, а что если произвольно упорядочить деревья, хотя бы по алфавиту?

>если $FOO и $BAR содержат только листья и мы их сравниваем - то дистанция равна дистанции Левинштейна(число операций insert/delete).

Да, и как я понял, сувествующие алгоритмы основаны на определении editing distance (к сожалению full text стоит денег).

>постараться найти такое поддерево $BAR, которое совпадает с поддеревом $FOO

Вот тут то и вся загвоздка Я тоже начал мыслить в этом направлении - находить ”соответствующие” друг другу поддеревья и сравнивать их. Но во первых, нахождение таковых выливается в самостоятельную, тоже нетривиальную подзадачу. Во вторых, в случае если дистанция заведомо большая, возможно что никаких схожих поддеревьев и нет вовсе, а схожести равномерно ”размазаны” по дереву. Остается одно - сравнивать все со всем, то есть global seqeunce alignment. Вопрос в том, как представить дерево в виде линейной последовательности. Хочу попробовать что то вроде recursive dynamic programming. Типа: если на одном уровне сравниваются два листа, то просто дистанция между ними. Если лист и узел - идти вглубь и сравнивать лист со всеми его подузлами, а в таблицу вставить - пока неясно, alignment score, или среднюю дистанцию (или ???). Если два узла - опять же - на один уровень вглубь и снова сравнивать.Насчёт сложности всей этой хрени пока подробно не думал, но по моему квадрат, как и при обычых строках.

[Ablertus]

Вот кстати статья, где эта хрень описана в подробностях

http://www2005.org/cdrom/docs/p76.pdf

Но боюсь, что некоторой модифицации подвергнуть все таки придется.

[Ablertus]

V poslednij raz byl zdes' bol'she mesjaca nazad. Neuzheli na etom forume algoritmy nikogo ne interesujut?

[Gypsy]

Originally Posted by Ablertus

V poslednij raz byl zdes' bol'she mesjaca nazad. Neuzheli na etom forume algoritmy nikogo ne interesujut?

You must be more specific:

I have to develop a function for counting distance. The simplest law is the following: 0 for match, 1 for mismatch, deletion or insertion. The more sophisticated functions take into account the similarity degree between mismatching nodes.

A simplest algorithm that would do this wuold just give you the percentage of matching subtrees. Very simple and works fine.

update:
-----------------------------

Compare(Tree1, Tree2):

if (Tree1 and/or Tree2 are Atomic): specific application-dependent comparison here, return 0 for total match, 1 for total mismatch

take all subtrees of Tree1: {S1, ..., Sn}
take all subtrees of Tree2: {P1, ..., Pm}

(it'd be better here if your subtrees in each node had a specific order)
(if not, the most general and least effective algorithm goes as follows)

Calculate a matrix (Cij), where Cij = Compare(Si, Pj)
For simplicity, most elements can be assumed to be 0 without calculation (how you do this depends on your application).

Find non-repeating indexes I1 ... Im that would minimize the sum:
Sum( C(Ij,j), j = 1..m )

I assumed n >= m, the opposite case is symmetric. In case n = m, and if the subtrees are somehow ordered, you could just take I1 = 1 ... In = n.

Store that minimal sum found in M

return (M / m)

-----------------------------

Now your goal is to reduce the number of recursive calls, which you can do if you have specific knowledge about the subtrees, how they are stored, if they are somehow sorted or not, etc.

[Gypsy]

One general trick that would largely reduce the number of comparisons is to store the height of each subtree, and compare only those subtrees whose heights are the same (or, say, differ insignificantly, depending on your application).

[Ablertus]

Thanks!