������ (original) (raw)

Mol. Genet. Microbiol. Virusol. vol. 3, pages 3-9, 1988, Russian

������ ������������� ��������������� ������� � ������������ �����������

�.�. �������, �. �. �������

���������������� ���������� ��� ������������ �������� � ��������������� ����� ��. �.�.������������ ���

�������� ������������� ����������� ���� ������������� �������� � ���������� ���������������� �������� �������� ��������� ���������� �������, ��������� ������������ ��������� ����������� ������������ �������� ����������� ������ �������������� ��������. ������ ������������������ ������������, �������� ������������ ��� ������������� ������������ ���� ������ ������������� ������ ��� ��� ���� ��������� � ����������� ����������� �� ��� ������ ����������������� ���� � ���������� ���� ���� � ������������ ����� ������. � ������ ������ ������� ��������, ��� ������� ����� �� � ��������� �����, �� � ������� �� ����� ������������� ����, ��� ������������ ���������������� ����� �������� ��������. ������, �������� �� �������������� �������������� ���� ������, �� ���������� ���� �� � ������������ ���� ���� ����������, ��������� ���������� �������������� ������������ ���� ������ ������������� ������������, ������������� ���������� ����� �������� ��� ���������� ������������.

��� ���������� ����������������� ���� �� ������ ������ �������� �������� ����������� ��������� ��������, ������� ������������ ������������ � ���������������� ������� ���������������� �����. �� �������� ����������� � ������������ ��������, � ������� ��������� ����� ������� ��������������� ��������� ������ �� �������������� ������� ������������������� ������������ � ������ � ����������� ������. �� ������ ������ ������� �������� ����������������� �����, �������, � ����� �������, ����� ���� ������������ ��� �������� �����������, � � ������ � ������ ��������� ������� � ������������ � ��������� ���� ��������.

����, ��� ������ ������������� ���������������� ����� �������� ����� ����� �� ��������� � ��������� �������������. ������� �� ����� ������������� � ���������������� ����� ������� �������������� ��������� � ����������, ������������ ������� ������ ���� ��������� ���������������� ������������. � ���� ������ �� ����������� ������ �������� � �������� ������������� � �� ����� ����������� �������� �������� �� ����� ������������� � ������������ ������. ��� �� �����, ���� � ���� ��, ��� ���������� ����� ������������ ����� ������������ ������������ ���������, ���������� �� ����������� ���������� ���������� ���������, �������� �� ���� �����. � ��������� ������ �������������� ������������� ����� �� ����������� ������ �������������� ��� ��������� �������. �� ���������� ������� � ���� ������ ��� � ������������� ����� ������, ������� ����������, ������� ������� ����������� � ����������������� ������, ��� � � ����� ������ ������ ������, � ��������� �������������� �������, �� ��������, �������� ����� ����� ������, ������� ������� ����������������� ����� ������������� ��������. ���� ������������� ���� �������� ������������� ��������������� ������� ������� � ������������� ������, �������� ���������, � ������������ ������� ���������� �������� � �������� ��������� ��������, ������������ � �������� ������. ���������� ����� �������� ����� ��������� ��������� ���������� �������������� ������� ��������� ����� ����� ��������� ������ �������� ���������� � ��������.

����� �������� ���������������� �������������� ������� ���������� ����������������� ����. ������ ��� ���������� � �������� ������������� ������, ������� ����������� �������� ���������� � ��������� ����� �������, ����������� ��� ���� ����. �������� ������������ ������ ������������� �������� ������������� ������ � ���� ������. ������ ����� ���� �������������� ���: ������ �� ������� ����������, ���������������� �������� ��������������� ���� ������� ������. � ��� ������ ���� �������� ������ ����� ���� ������������ � ���� ������, � ������� ���������� ����� ������ � �������� ������������� ����������� �� �������� ������, �� ��� ������ � ��������������� ������ �������� �����������. ������, ���������� ��� ��������� ������������������� ������������, ��� � ����������� ����������� ������ ������������� ������, ������ ����������� �������������. � ������ ������������ ��� ������� � ������������� � ���������� ��������, ������������� � ���� ��������. ������� ������ ���������� ������������� �������� � ��������� ������, ������� ����������� ������������� �������� ������. �������� ��������� �������� ������������. ������������� � �������� �������� ������������ ����� ��������� ������������� ���������� ���������� ����� ������ �� �������� ������ �� ���������� � ����������� ������ [11]. �������, ����������� ���� �������, �� ������ �������������������. ����������� ������ ������� �������� �������������� ����� ��������� ������ � �������������� ��������� ���������� ������, ��� ��� �������� ������� ��������� ��������� ��������� ��������, ������� ������� �������� ��������������� ���������. ����� ����, ������ ������������ ����� ���������� ����� ������ � ���������� �������� ����������� �������, ��� �� �������� ������. � ���� ������� ����� ��������� ������ ����� ��������� ��������������. ��� ���������� ���������������� ����������������� ����� ����. ������� � ��������� ����� �� �������� � �������� ������������ ���������� ������ � ������, ���������� �� �������� ������������ ��������.

������ ������ ����������������� ������� ������������ ��������. ����� ��� �������� ������� ���������� ����� ������ �� ���������� ���������. ����� ������� ������������ �������� ���������� ������, ��������������� ��������� ��������.

1. ��������� �������� ������ ������ ��������� � ���������� ������������� �����.

2. ����� ���� ����� ������ �� ������������.

3. ���������� ����� ����� ������ ��������� � ������ �� ������ ���������� ����� ���������������� �� ������ �� �������� ������.

4. ����� ���� ����� ������ �� ������ ����� ���� ����� ������ ������, ���������������� �������� 13.

����������� 13 ����� ����� ������������� �����, � ����������� 4 �������� �������� ������������ �������� [7], �������������, ��� �������� ��� ������������� �������� �������������� ����� ���� � ���������� ������ ������������ �������.

� ��������� ����� ���� ������� ����� � ������ ����������� ������������ � ������������ ������� ���������� ���������� ����������������� ����. ��, �������� �� ���� ������������, ���� ������ �� ������ ���������� ������������������.

��-������, ������� ������������ �������� ����� ��������� ����������� ��������, ��� ��� � ������� ����� ������������ ������� � �������� ����. ������� ������ �� ��� ������������� ��������� ���. �������� ����� ��� ����� ������ �������� � ������ �. �. ��������� [2]: ������� ������������ ���������� ����������� �������� �� �������� �������� ������������ �� �������� ������� ��� ��������.

��-������, ��� ������� ����������, ������� ������������ �������� ����������� � ��������� ���������� ������. ��� ��������, ��� ��� ������ � �����������, ������������ �� �������� ������������ ��������, ������������ �������� ��������, �����, ��������, �������������� ��������� ������ �� ����� ���� �������, ��������, �� ��������� ��������� ������������� Lepidoptera, �������� �� ����� ��������� ��������� Diptera ��� ���� ����� ������� ��������������� ����� [14].

�, �������, � ��������� ����� ���������� ���������, �������� ������� ������� ������������ �������� �� ���������� �����. ����� ����, ��������, ��� ������ ���������� ������ ������������ �������� ����������� � ������ ��� ���������� NP������ �����, ��� ������, ������ ������������� ����������� ������������� ����� ���������� [13]. ������� ����������� �� �������� ��������� �������� �������������, �. �. ������ �� ���� ������� ������������ ��������, � ������ ����������� � ���, � ��� �� ������ ������������ ��� ������.

� ����� � ���� �� ������ ������� ��� ���������� ����������������� ���� ���������� ���������� ������. ��� ������������� ����������, ������ �� ����������� ������������ ������������� ��������� ������ ���� ��� ���������� ������. ����� �������, ������, ���������� ���������� �������, �� ������� ���������� ����� ��������� ��������� ���������� ������, ����� ����������� �� ���� ����������. �������� ��������, �������� ���������� ������ ������������ ��� ���������������� �������������, �������� ������������� ���� ������� ��������� � ����������� �������� �������� � �� ��������� �� ���� ������������ ������.

������� ������������ ������� ���������� �������������� ��������� ���������� ����������������� ����, ������� ���� �� ��������� ��� � ��������������� �������� ��������, ��� � � ��������� ���������� ������, ��������� ��������, ����������� ��� ��������� �������� ����������, � ����������� ����� ������ �� ���� �� ����������.

� ����� ������ ��� ������ ����� ������� �� 2 ���������������� ����������� �����: ����� ����������� ��������� (���������) ������ � ����������� ����������� ���� ������. ��������, ��� ����������� ����� ��������� ������ �������� ����������� ����� ������ ������� �� ��������� � ������������ ���������� �������� ���� ������ ������. ������ ������ �������� ����������, � �������� ��������� ������������ 1� ����. ��� ������� ���� ������ ������������� � ������������ ������� ��������� �� ���������� ���������� � ������������� �������� �������� �� ������ ����� ��������� ������. ����� �������������� ������ ��� ��������� W. Fitch [10]. ��� �������� ����� ������ ���������� ������ ��������� ������������� �����������. ������ ���������� ��������� ���������, ���������� ���������, � ����������� �� �����. ��� ���� ����� 2 ������� ��������� ������������ ����� �����, �. �. � ������ ����������� �����. ���������� ����� ��������� � ��� ����� ���� �����, �������� � ��� ����.

��������� �������� �������� � 4 �������� ���������.

� ������ ������ W. Fitch ����� ������� ��������� ������ ������, ��� ��������� �������� ���������� ����������� ������� 4 ������, ������� ���� ������� �������������� �. �. ���������� [3] � �. �. �������� [11, � ����� ����������� P. Bunneman [5, 6] � J. Dobson [9].

������� ����������� � ���������. ������� ���������� ����� �������� ��������� ������ ���������� ��� � ��������� �� ������ ������� 2 � ����� ������� �����; ������ ������������ ������� ���������� ����� ���� ����� ����������� ���������� ������� ����� � ������ �����, ����� ��� ������������� ������� 4 ������: ��� ����� ��������� ����� i, j, k, l �� 3 ���� ���������� dij +dkl, dik+ djldil + djk 2 ����� � �� ������ �������.

��� ���� ����� ������ ����� ������� 4 ������, ���������� ������������� � ������������ ������ 4 ��������� ������� i, j, k, l � ����������� ��������� (i, j, k, l), ������������ �������� ������, ������������ ������� i, j, k, l ����� �����. ����� ������, ��� ��� � ��������� �� ������ ������� 2 ��������� � ����� �� �������� �� �������. ����� ��� �������������� ��� ��������� � �1. �����

dij+dkl < dik+djl = dil+djk

� ����� �������� ���� dlk+djl, dii+dik ������ ����� dij+dkl �� ��������� ����� ������������ ����� � _T_1. ��������� �� ���� 3 ���� ������������� ������������ ������, ����� ����� ������������ ����� ����� 0 � � (i, j, k, l) ��������� � _T_4�� �������.

����� �������� ��������� �� ������� � ������, ���� ����� �������� ��������� ����������� ������ ��� ������ ������: 1 ���������� �������� � 2 �������. ��������, �� ������� ��������� ����� ������� i. jk, l. To��� ��������, ��� �� ����� ����������� 4 ������ ��������� �������� ��������� ���������� ����� ������ ������ � �����, ������� �����, ��� ��� � ������� �� ���� ��������� ���������� � ���������� ����� �������� �� ������ ����� ������������ (�����������) �����. ����, ��������� ������������ 4 ������, ����� �������, �� ���� ������, ���������� �� ����������� ����� �������� ���������, ����� ���� �������� ���������.

��������, ��� ��������� ������ ���� i, j � ��������� ��������� ������� �� ����, � ������� ����� �������� ����� �� ������������� ��� ���������. ��������� ������ ��� ���������� ������� �������� ��������� [15]. �������� �������� ��������� ����� �������� �������� ������� _DN_= || dnij || , � ������� dnij ����� ����� ��������, � ������� ������� ���� i, j ������� � ��������� ���������.

�������, ��� ������� �������� ��������� ����� �������� ��� ��� ������������ ������, ��� � ��� ����, ��������� ������������ 4 ������ ��� ������� ������� ����������.

������� ����������� � ��������� � ����������� 4 ������ (1) ����������� ��� ��� ���������� ���������� ������ ���������� � �������� ����������� � ����������� �������� ������������. ������, ��� ��� ����������� �� ��������, � ����������� ����� �������� ������� ������� ���������� �� �������� �����������, �, �������������, ����������� (1) ���������� ���� �� ��� ����� ��������. ������ ��������, ��� � ����� ������ 4 ���� ����� ���������� ������� i, j, k, l ���, ���

dij + dkl £ min (dik + djl , dil + djk) . (2)

�������, ��� ������� (2) �������� ����� ������ �� ��������� �

dij + dkl £ dik + djl = dil + djk (3)

� ������� ���������� ����������� �������� 4 ������ [15]. ��������� ���� ��������� ��������� � ���������� �������, ����� ���������� �������� ���� i, jk, l, ��������������� ����������� (2), ��������.

W. Fitch ��������� � �������� ������, �������� ���������������� ������� ���������� D, ����� �, ��� �������� ������� |DN (D) � DN (T)|, ������ ����� ������� �������� ����� ���������������� ���������� ������ �������� ���������, ����������.

� ���������, �� ��������� ������ ���������� ������� ���������� ���������, ����������� ���������, ������������� �� ������ ������� ������� �������� ��������� ���������� ������. ������� ���� ���� ��� ��������, ��� ������ ������� ������� N �������� �������� �������� ��������� ���������� ������, �� ������������ ��������� ��� ������ ���������� ������ ������ ������� � �������� ���� �������� � N �������� ��������� (�. �. ��� ��� 10 ����� ���������� ��������� 2 027 025 ��������, ���� �� ������������� ������ �������� �������, �

4 093 236 352 ������, ���� �� ��������� ������������ ���������������� �������) [12]. �, �������, �� �������� (����, �� ���� ���������, ��� ���), ��� ������� �������� ��������� ���������� ���������� ��������� ������, �. �., ������� ������� W. Fitch, �� �� ����� ������������� ������������� ������� ���� ��� ���������� ������. ������� �������������� ����� W. Fitch ������������� ���������� �� �����.

������� ������������� ��������������� �������. �������������� ������� � ������������. ����� ������ ������ ���������� ������ � ����������� ����������, ���������� ������� ��������� ������� ��� �������������� ��������� �������� � ����������� ����� ����� �������� � ������ �������� ����������. W. Fitch [10] �������������� ��� ����� ��������� �������� ��������� (��. ���������� ������), ������ ���� ������ �� �������� ������������ ��� ����� �������. ������ ��� ������������� �������������� ������������� ������������ ������� �������� ��������� � ��������� ������, ��������, ��� ����� ������� ���� ����� ����� ������������� ��������� ������. ����������� ����� ������ �������� �������� ��������� ������ �������� ������������ ����������� 4 ������ ��� ������ �������� ����� �� ������. �� ������� ����������� � ��������� �������, ��� ���� ��� ���������� ������ ��������� ��������� (i, j, k, l) [��������� (i, j, k, l) � ��������� �� ������ ������� 2 � ����� ����� 0), � �� ���������� �������� ���� ��� �����, �� ��� ���������� ����� ������ �������� ����������� ����� ������� dij+dkl, dik+djl,, dil+djk, � �� ���������� �������� �������� � ��� ����� ����������.

�����������, ��� ����������� ����������� ����������� � ��� ������������� ������. � ������, ���� ��� ���������� ��������� ������, � �� ���������� �������� ���� ��� �����, ��, ��� �������� � ������ �. Colonius � �. Schulze [8], ���������� ����� �� ���� ������� ���������� ����� �������� ��������� ������, � ������ �������� ����������� ����� ������� dij+dkl , dik+djl , dil+djk ��� ������ �������� ������� ������. ����� �������, ��� ������� ��������� ������ ���������� ����� ��������� �����������, ������������ ������ ��������� (i,j,k,l).

��� ����� ������ ��������������� ��������� ���������. ������� �� ��������� ���� �������� ������� ������ ������ ������� FT ��������� �������:

FT (i, j, k, l) = 1, ���� ��������� (i, j, k, l) ��������� � �1 �� �������;

FT (i, j, k, l)=0, ���� ��������� (i, j, k, l) ��������� c �4; �� ���� ��������� ������� ������� �� ����������. �� ������� 4 ������ �������, ��� ������� FT ����� ���� ������, �������������, �����������:

FT(i, j, k, l)=1, ���� ��������� ������� (1); FT(i, j, k, l)=0, ���� ��� 3 ����� �� (1) �����; �� ���� ��������� ������� ������� �� ����������.

����� ������, ��� FT ������������� ��������� ��������:

I. ���� FT ���������� ���� �� ����� �� ������� ijkl, klij, lkij, �� ��� ���������� �� ���� 3 � �� ���� ��������� ���� � �� �� ��������.

II. ���� FT ���������� ���� �� ����� �� ������� ijkl, ikjl, iljk, �� ��� ���� ���������� ����� �� ����� �� ��� � ����� �� ��� 1, ���� ��� ���������� �� ���� 3 � ����� �� ��� 0.

����� ������ �������� ��������� ����� S � �� ����� ������������ �� ��������� �������� �� S ������� F, ����������� �������� 0 � 1 � ��������������� �������� I � II. ����� ��������, ��� F ����������� �������, ���� ���������� ������ � ���������� ������� ������ S, �����, ��� F=FT. �. Colonius � �. Schulze [81 ����� �������� ������������� ������� F ������� � ��������, ��� ����� ���������� �����������. ���� �������� ���������� ��������� � �� ���� ������ ������� ���������� ������, ������������ ������� F. ������� ����� ������� �������������� ����������� ��������� �������, ������� � .������ ��������� ������ ����������. � ������ ����������� ��������� �������, ������� �� ����� ��� ��������������.

�������. ������� F ����������� ������� ����� � ������ �����, ����� �� �������: F (i, j, k, l) � F (i, k, l, m) ����������, �������, ��� F (j, k, l, m) ���������� � ����� F (i, k, l, m).

��� ���� �������� ����, ������� FT , ���������� ��������������� ��������� ����������� ������, ������������ ���������� �������, ����� ���� ������� ��������������� �� ������� ��� ��������� � ������. ����� ����� ����� ���������� �������� � �������� FT, ��������������� ��������� ������������ ������� ������, ��������� �������� � �������������� ��������� ���������� �������, ������������ �������� FT.

������� ����, ��� ��� ���� ������� � ���������� ���������, ������� ������ � ������������� ������ � ���������� ������������ ������� ���������� D. ��������� ������� FD ��������� �������: ������� FD (i, j, k, l) ���������� ����� � ������ �����, ����� ����� ����� (2); ������ FD(i, j, k, l) = 1_,_ ����� ����������� � (2) �������, � _FD(i, j, k, l)_=0, ����� � (2) ����� ����� ���������.

����, ��� ������� FD ������������� �������� III. �������, ���� 2 ����� ������� FDFD' ��������� �� ��������� ������ ijkl, �� ��� ��������� �� ���� �������, ���������� �� ijkl ������������� ����������. ��� ��������� ������ ��� ����� ������� ���������� \FDFD'\ ��� ����� ��������� �������� (i, j, k, l), �� ������� FD �� ����� FD'.

����, ��� ���� ������� FD ����������� ��������� �������, �� ��� ������ ������������ � ��������� �� ������ ������� 2 � ����� ������� �����, � ������� FDFT ���������.

������� �������������� ������������ �������� � �������� ������, �������� ���������������� ������� ����������, ����� ����� ������, ��� �������� |FD�FT| ����������. �������� |FD�FT |, ������ ����� ��������, ��� ������� �������� FD � FT �� ���������, ����� ����� �������� �������������� �������������.

����� ������ � ������ ���������� ����������������� ������, �������� �� ����� ���� ����� ��������� ������, � ������������ ������� ���������� ������ �������������� ��������� ������ ����������, ������� ��������� ������������� ��������������� �������. ������������ ������ ������� ������� � ���������.

1. � ������� �� ����������� ����������� �� ��������� ������ ������� ���������� ���������������� �������� ������� ������������� ��������������� ������� �� ������ ������� �������������� ��������� � ���� ������������� �������� � ��������� ��������.

2. ��� ���������� ������ ����� ���� ������ �������.

3. ����� �������������� � ����� ������������ �������� ������.

����� ����� ������� ��������� � ����� ��� ��������� �������� {i, j, k, 1} �� 3 ���� _s_1=dij+dkl, s_2_=dik+ djl � _s_3=dil+djk 2, ������ _s_1� _s_2, ����� � ����� ������ 3�, ����� ����� ����� ����������� ���������� _s_1 ��� _s_2 ��� �������� � ���� ���������� �������� ������������ �������, �� �� ������ �������� ������� FD �, �������������, �� �������� �� ������������� �������. ����� �������, ����� ������, ��� ������� FD ����������� �������, ���� ������ ���������� ������.

  1. ������� |FD�FT| ���� ������� ����������� ������ ������ ������������ ��������� ������������ ������ �������� ������� ����������. ���, � ���������, ��������� ���������� ����� ����� ���������������� �������, ����������� �� ������ ���������, �. �. ��������� ������ ������, ������� ����� �������������� ����� ���������� ������ �������������.

5. ��������� ������� FDFT �� ���� ������� ��������, ���������� ��������� ������������ ��� ���, ��������� �������� �������������� ������ ���������� ��� ��������� � ���������� ��������� �� ������ � ���� �������� ���������� ��������������� ������������. ����� �������, ���������� ����������� ������������ ����� � ����������� ��������, ������� ������� ����� ���������� ���������.

6. ����� ��������� ������� ����������������� �����, ����������� ���������� � ������ ���������, ���������� � �������� ��������� �����������. ��� ���� ����� ������������� ���������� ������ ���������, � �� ����� ���������� � ���������� �������� ��������.

7. � ������� �� ��������������� ������ W. Fitch ������� ������������� ��������������� ������� ��������� � ����� ����� �������� ��������� ���������� ��������. 2 ���������, ����������� ������� ������������� ��������������� �������, �������, �������������� ���������������� ���� ������������, � ����� ���������� ������������� ��������������� ������������� �������� ����� ��������� � ������������� ������ [4].

����������

1. �������� �. �. ������ �������. ����. � 1965. � �. 20. � �. 94�96.

2. �������� �. �.�������� �����������: �������� ������ ��������. �., 1975. �. 117147.

3. ���������� �. �.����. ��������. ���������� � �������. ������. 1962. �. 2.�. 371�372.

4. ������� �. �., ������� �. M.// �������. ��������. � 1988. � � 3. � �. 9.

5. �������� P.//J.combinat. theory. � 1974. �Vol. 178. � P. 48�50.

6. �������� �. // Mathematics in Archaeological and Historical Sciences / Eds F. R. Hodson et al. � Edinburgh, 1971. � P. 387�395.

7. CavaliSforza L. L., Edwards W. F // Evolution. � 1967. � Vol. 32. � P. 550�570.

8. Colonius H., Schulze H. H. // Brit. J. math. Statist. Psychol. � 1981. � Vol. 34. � P. 167�180.

9. Dobson J.//J. appl. Probability. � 1974.�Vol. 11. � P. 32�42:

10. Fitch W. M.//J. molec. Evolut. � 1981. �Vol. 18. � P. 60�67.

11. Fitch W. M., Margoliash E.// Science. � 1967. � Vol. 155. � P. 279�284.

12. Foulds L. R., Robinson. R. W. // Combinatorial Mathematics. Berlin, 1980. Vol. 7 P. 110126.

13. Graham R.L., Foulds L.R. //Math. Biosci. � 1982. � Vol. 60. � P. 133� 142.

14. Rohlf F. J. // Syst. Zool. � 1984. �Vol. 33. � P. 341�343.

15: Sattah S., Tversky A. // Psychometrica. � 1977.�Vol. 42. � P. 319�346.

��������� 18.06.87

Maximum Topologic Similarity Principle in Molecular Systematics

K.M. Chumakov, S. V. Yushmanov

The paper deals with the problem of phylogenetic reconstruction on the basis of comparative analysis of features. Main attention is paid to comparison and classification of the biopolymer sequences. Different approaches to this task are critically reviewed. The novel principle of construction of treelike classification schemes permitting subsequent evolutionary analysis is proposed. It concentrates on reconstruction of the tree with a topologic structure that is most close to topologic features, imprinted in the source distance matrix. Realization of this approach was made possible by development of the special formalism, enabling evaluation and comparison of topologic features of distance matrices and trees.