Филогенетикалық ағаштарды құрудағы «қосылатын көршілер» әдісі

Кіріспе

Филогенетикалық ағаштарды құру үшін төменнен жоғары кластерлеу әдісі. Биоинформатикада "көршіні қосу" – 1987 жылы Наруя Сайтоу және Масатоси Ней жасаған филогенетикалық ағаштарды құруға арналған төменнен жоғары (агломеративтік) кластерлеу әдісі. Әдетте ДНК немесе белок тізбегінің деректеріне негізделген бұл алгоритм филогенетикалық ағаш құру үшін әрбір таксон жұбының (мысалы, түрлер немесе тізбектер) арасындағы қашықтықты білуді талап етеді.

Күрделілігі

Таксандар жиынтығына көрші қосылу итерацияларды қажет етеді. Әр қадамда матрицаны құру және оны іздеу қажет. Бастапқыда матрицаның мөлшері , кейін келесі қадамда , және т.б. Бұл әдісті тікелей іске асыру уақыт күрделілігі бар алгоритмге әкеледі; бірақ эвристика қолданатын іске асырулар орташа жағдайда одан әлдеқайда жақсы нәтижелер береді.

Бірінші тармақ ұзындығының бағасы

Жаңа түйін деп белгілейік. Жоғарыдағы теңдеуге сәйкес, және түйіндерін түйінімен қосатын тармақтардың ұзындығы:

Көршілердің қосылуы ең аз эволюция ретінде

Көршілердің қосылуын теңгерімді ең төменгі эволюция (БМЭ) критерийінің ашкөздік эвристикасы ретінде қарастыруға болады. Әрбір топология үшін БМЭ ағаштың ұзындығын (бутақ ұзындықтарының қосындысы) арақашықтық матрицасындағы қашықтықтардың салмақталған жиынтығы ретінде анықтайды, ал салмақтар топологияға байланысты. БМЭ оптималды топологиясы – бұл ағаштың ұзындығын ең көп азайтатын топология. NJ әр қадамда ағаш ұзындығының ең үлкен кемуін қамтамасыз ететін таксондардың жұбын ашкөздікпен қосады. Бұл процедура БМЭ критерийі үшін оптималды шешімді табуға кепілдік бермейді, бірақ көбінесе оны табады және әдетте оған өте жақын болады. Бұл жүздеген немесе мыңдаған таксондардан тұратын үлкен деректер жиынтықтарын талдауды және бутстрапті жүзеге асыруды практикалық етеді, себебі басқа талдау әдістері (мысалы, максималды үнемділік, максималды ықтималдық) осы мақсаттар үшін есептеу жағынан қиын болуы мүмкін. Көршілердің қосылуының қасиеті бар: егер кіріс арақашықтық матрицасы дұрыс болса, шығыс ағашы да дұрыс болады. Сонымен қатар, шығыс ағашының топологиясының дұрыстығы, егер арақашықтық матрицасы «жақын қосылатын» болса қамтамасыз етіледі, яғни арақашықтық матрицасындағы әрбір элемент ағаштағы ең қысқа бутақтың жартысынан кем емес нақты қашықтықтан өзгеше болады. Іс жүзінде арақашықтық матрицасы бұл шартты сирек қанағаттандырады, бірақ көршілердің қосылуы көбінесе дұрыс ағаш топологиясын құрастырады. Жақын қосылатын арақашықтық матрицалары үшін көршілердің қосылуының дұрыстығы эволюцияның көптеген модельдері бойынша статистикалық тұрғыдан сәйкес келеді; жеткілікті ұзындықтағы деректер болған жағдайда, көршілердің қосылуы нақты ағашты жоғары ықтималдықпен қайта құрастырады. UPGMA және WPGMA-мен салыстырғанда, көршілердің қосылуының артықшылығы бар: ол барлық туыстамалар бірдей жылдамдықпен эволюцияға ұшырайды деген қағиданы (молекулалық сағат гипотезасы) қабылдамайды. Дегенмен, көршілердің қосылуы көбінесе қашықтық өлшемдеріне сүйенбейтін және көп жағдайда жоғары дәлдік ұсынатын филогенетикалық әдістермен ығыстырылды. Көршілердің қосылуының кемшілігі бар: ол кейбір бутақтарға теріс ұзындық тағайындауы мүмкін.

Neighbor joining may be viewed as a greedy heuristic for the balanced minimum evolution (BME) criterion. For each topology, BME defines the tree length (sum of branch lengths) to be a particular weighted sum of the distances in the distance matrix, with the weights depending on the topology. The BME optimal topology is the one which minimizes this tree length. NJ at each step greedily joins that pair of taxa which will give the greatest decrease in the estimated tree length. This procedure does not guarantee to find the optimum for the BME criterion, although it often does and is usually quite close. This makes it practical for analyzing large data sets (hundreds or thousands of taxa) and for bootstrapping, for which purposes other means of analysis (e. g. maximum parsimony, maximum likelihood) may be computationally prohibitive. Neighbor joining has the property that if the input distance matrix is correct, then the output tree will be correct. Furthermore, the correctness of the output tree topology is guaranteed as long as the distance matrix is 'nearly additive', specifically if each entry in the distance matrix differs from the true distance by less than half of the shortest branch length in the tree. In practice the distance matrix rarely satisfies this condition, but neighbor joining often constructs the correct tree topology anyway. The correctness of neighbor joining for nearly additive distance matrices implies that it is statistically consistent under many models of evolution; given data of sufficient length, neighbor joining will reconstruct the true tree with high probability. Compared with UPGMA and WPGMA, neighbor joining has the advantage that it does not assume all lineages evolve at the same rate (molecular clock hypothesis). Nevertheless, neighbor joining has been largely superseded by phylogenetic methods that do not rely on distance measures and offer superior accuracy under most conditions. Neighbor joining has the undesirable feature that it often assigns negative lengths to some of the branches.