Кіріспе

Математика, компьютерлік ғылым және әсіресе граф теориясында қашықтық матрицасы – жиын құрамындағы элементтер арасындағы жұптық қашықтықтарды қамтитын квадрат матрица (екі өлшемді массив). Қолданылатын саласына байланысты, осы матрицаны анықтау үшін қолданылатын қашықтық метрикалық қасиетке ие болуы да, болмауы да мүмкін. Егер жиында N элемент болса, онда матрицаның мөлшері N×N болады. Граф теориясы саласында элементтер көбінесе нүктелер, түйіндер немесе төбелер деп аталады.

Метрикалық емес қашықтық матрицасы

Жалпы, қашықтық матрицасы – белгілі бір графтың салмақталған тұтастық матрицасы. Желіде, доғаларына салмақтар тағайындалған бағытталған графта, желідегі екі түйін арасындағы қашықтық екі түйінге жалғасқан ең қысқа жолдардағы салмақтардың қосындысының ең кіші мәні ретінде анықталады. Бұл қашықтық функциясы жақсы анықталғанмен, метрика емес. Салмақтарды біріктіру және салыстыру қажеттілігінен басқа, оларға ешқандай шектеулер қойылмайды, сондықтан кейбір қолдануларда теріс салмақтар қолданылады. Жолдар бағытталғандықтан, симметрия кепілденбейді, және циклдар болса, қашықтық матрицасы толық болмауы мүмкін. Жоғарыда айтылғандардың алгебралық формуласын min+ алгебрасын қолдану арқылы алуға болады. Бұл жүйеде матрица көбейтуі келесідей анықталады: екі n × n матрица және олардың арақашықтық көбейтіндісі n × n матрица ретінде анықталады, сондықтан тікелей байланыспаған диагональдық элементтерді шексіздікке немесе min+ операцияларының дұрыс жұмыс істеуі үшін қолайлы үлкен мәнге орнату қажет. Бұл орындардағы нөл қашықтығы, құны және т.б. жоқ жиек ретінде қате түсіндіріледі. Егер W – графтың жиектерінің салмақтарын қамтитын n × n матрица болса, онда (осы арақашықтық көбейтіндісін пайдаланып) ең көп дегенде k жиегі бар жолдар арқылы түйіндер арасындағы қашықтықтарды береді, ал – графтың қашықтық матрицасы болып табылады. n төбесі бар кез келген G графигін n төбесі бар салмақталған толық граф ретінде модельдеуге болады, G графигінің жиегіне сәйкес келетін толық графтың әр жиегіне бір салмақ тағайындап, қалған барлық жиектерге нөлдік салмақ қояды. W бұл толық граф үшін G графигінің тұтастық матрицасы болып табылады. G графигінің қашықтық матрицасын W матрицасынан жоғарыда көрсетілгендей есептеуге болады, бірақ дәстүрлі матрица көбейтуімен есептелген мән екі түйін арасындағы дәл n ұзындығындағы жолдардың санын ғана көрсетеді.

Биоинформатика

Қашықтық матрицасы биоинформатика саласында кеңінен қолданылады және бірнеше әдістерде, алгоритмдерде және бағдарламаларда кездеседі. Қашықтық матрицалары белок құрылымдарын координаттарға тәуелді болмай, екі тізбек арасындағы қашықтықты тізбек кеңістігінде көрсету үшін пайдаланылады. Олар құрылымдық және тізбектік теңестіруде, сондай-ақ ЯМР (NMR) немесе рентгендік кристаллография арқылы белок құрылымдарын анықтау үшін қолданылады. Кейде деректерді ұқсастық матрицасы түрінде беру ыңғайлырақ болады. Ол қашықтық корреляциясын анықтау үшін де қолданылады.

Тізбелік сәйкестендіру

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

Жалпы сәйкестендіру

Глобалды сәйкестікті есептеу үшін қолданылатын Нидлман-Вунш алгоритмі қашықтық матрицасын алу үшін динамикалық бағдарламалауды пайдаланады.

Жергілікті сәйкестендіру

Смит-Уотерман алгоритмі де динамикалық бағдарламалауға негізделген, ол қашықтық матрицасын есептеуден және содан кейін жергілікті тізілімді табудан тұрады.

MAFFT

Тез Фурье түрлендіруін (MAFFT) қолданатын көптік сәйкестендіру – прогрессивті сәйкестендіруге негізделген алгоритмі бар бағдарлама, және ол әртүрлі көптік сәйкестендіру стратегияларын ұсынады. Біріншіден, MAFFT ортақ 6-дық топтардың санына негізделген қашықтық матрицасын жасайды. Екіншіден, ол бұл матрицаның негізінде бағыттаушы ағашты құрастырады. Үшіншіден, ол жылдам Фурье түрлендіруін пайдаланып тізбектерді кластерлейді және сәйкестендіруді бастайды. Жаңа сәйкестендіру нәтижесінде, ол бағыттаушы ағашты қайта жасайды және қайта сәйкестендіреді.

Филогенетикалық талдау

Филогенетикалық талдау жүргізу үшін алғашқы қадам – филогенетикалық ағашты қайта құру: түрлер жиынтығы берілген жағдайда, мәселе түрлер арасындағы туыстық байланыстарды анықтау немесе қорытындылау, яғни түрлердің филогенетикалық ағашын құру болып табылады. Бұл жұмысты қашықтық матрицасы әдістері іске асырады.

Қашықтық матрицалық әдістері

Филогенетикалық талдаудың қашықтық матрицалық әдістері жіктелетін тізбектер арасындағы "генетикалық қашықтықтың" өлшемдеріне тікелей сүйенеді, сондықтан кіріс ретінде бірнеше тізбек қажет. Қашықтық әдістері тізбектер жиынтығының әрбір жұбы арасындағы қашықтықты сипаттайтын толық матрицаны құруға тырысады. Осыдан, бір-бірімен тығыз байланысты тізбектерді бір ішкі түйінге біріктіретін және тармақтарының ұзындығы тізбектер арасындағы байқалған қашықтықты шамамен көрсететін филогенетикалық ағаш салынады. Қашықтық матрицалық әдістер қолданылатын алгоритмге байланысты тамырланған немесе тамырланбаған ағаштарды құра алады. Егер n түр қарастырылса, кіріс – n × n өлшемді қашықтық матрицасы M, мұнда Mij – i және j түрлері арасындағы мутациялық қашықтық. Мақсат – қашықтық матрицасына сәйкес келетін 3-дәрежелі ағашты шығару. Бұл әдістер көп реттіліктерді сәйкестендірудің прогрессивтік және итеративтік түрлері үшін жиі қолданылады. Қашықтық матрицалық әдістердің басты кемшілігі – бірнеше тармақта кездесетін жергілікті жоғары өзгергіштік аймақтары туралы ақпаратты тиімді пайдалана алмауы.

Фич-Марголиаш

Фитч-Марголиаш әдісі генетикалық қашықтыққа негізделген кластерлеу үшін салмақты ең кішкентай квадраттар әдісін пайдаланады. Туыстығы жақын тізбектерге ағаш құру процесінде үлкен салмақ беріледі, бұл алыс туысқан тізбектер арасындағы қашықтықты өлшеудегі қателікті азайтуға мүмкіндік береді. Осы қашықтықтарға қолданылатын ең кішкентай квадраттар критерийі көршілерді қосу әдістерінен дәлдігі жоғары, бірақ тиімділігі төмен. Деректер жиынтығындағы көптеген туыстығы жақын тізбектерден туындаған қашықтықтар арасындағы корреляцияны түзетуге мүмкіндік беретін қосымша жақсартуды есептеу күшін арттыру арқылы қолдануға болады.

Деректер өндіру

Деректерді зерттеудегі (мәліметтерді талдаудағы) жиі қолданылатын әдіс – берілген деректер жиынтығына кластерлік талдау қолданып, деректерді басқа топтармен салыстырғандағы ұқсастық деңгейіне қарай топтастыру. Ұқсастықты қашықтық өлшемі арқылы бағалауға болатындықтан, кластерлік талдауда қашықтық матрицалары кеңінен қолданылады және маңызды рөл атқарады. Осылайша, қашықтық матрицасы жиынтықтағы барлық деректер жұптары арасындағы ұқсастықты көрсететін шама болып табылады.

Машиналық оқыту

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

Компьютерлік көру

Қашықтық матрицасы бейнелерді болжауға арналған машиналық оқыту модельдеріндегі нейрондық желілерде 2D-ден 3D-ге регрессия үшін қолданылуы мүмкін.

Гаусс аралас қашықтығын пайдаланатын қашықтық матрицалары

Ақпаратты іздеуде нақты ең жақын көршілерді табу үшін Гаусс қоспасы қашықтығы қолданылады. Деректер қорындағы деректердің таралуын сипаттау үшін белгілі бір Гаусс шекті қоспасы моделі негізге алынады, ал Гаусс қоспасы қашықтығы іздеу деректерінің таралуы мен деректер қорындағы деректердің таралуы арасындағы Куллбек-Лейблер дивергенциясын азайту арқылы құрастырылады. Дәлдік бойынша өнімділікті өлшеу негізінде Гаусс қоспасы қашықтығының, жақсы белгілі Евклидтік және Махаланобис қашықтықтарымен салыстырылған нәтижелері, әртүрлі сынақ деректері үшін Гаусс қоспасы қашықтығы функциясының артықшылығын көрсетеді. Ақпаратты іздеу саласындағы маңызды алгоритмдердің бірі – Балық мектебін іздеу алгоритмі, ол балық мектебінің ұжымдық мінез-құлқының жиналуы үшін қашықтық матрицаларын қолданады. Олардың салмағын жаңарту үшін тамақтану операторын пайдалана отырып.

Eq. A:

Eq. B:

Stepvol – қашықтық матрицасымен, атап айтқанда Евклидтік қашықтық матрицасын қолдана отырып, ең жоғары көлемдік орын ауыстыру мөлшерін анықтайды.

Косинус ұқсастығы мен қашықтық матрицаларының ұқсастығы мен ұқсамастығын бағалау

Косинус ұқсастығы өлшемі ақпаратты іздеуде ең көп қолданылатын жақындық өлшемі болып табылады, себебі ол іздеу кеңістігіндегі құжаттар арасындағы бұрыштарды косинус негізінде өлшейді. Евклидтік қашықтық орташа мәнді түзетуге өзгермейді. Орташаның ықтималдық үлестірілімі бір популяциядан бірнеше рет іріктеме алу және алынған іріктемелік орташа мәндерін тіркеу арқылы құрастырылады. Бұл әртүрлі орташа мәндердің үлестірілімін қалыптастырады, ал осы үлестірілімнің өзіне тән орташасы мен дисперсиясы болады. Оң және теріс мәндерді қабылдайтын деректер үшін косинус ұқсастығының нөлдік үлестірілімі екі тәуелсіз кездейсоқ бірлік векторларының скалярлық көбейтіндісінің үлестірілімі болып табылады. Бұл үлестірілімнің орташа мәні нөлге тең, ал дисперсиясы 1/n-ге тең. Евклидтік қашықтық осы түзетуге инвариант болады.

Кластерлік құжаттар

Ұқсас құжаттарды ұйымдастыру және топтастыру үшін қашықтық негізіндегі метрикаларды қолдана отырып, иерархиялық кластерлеуді іске асыру қашықтық матрицасын қажет етеді және оны пайдалануды талап етеді. Қашықтық матрицасы бір құжаттың екінші құжатпен байланыс дәрежесін көрсетеді, бұл пайдаланушы сұранысына сәйкес тиісті құжаттарды іздеу әдістерінде қолданылатын жақын байланыстағы құжаттардың кластерлерін құру үшін пайдаланылады.

Изомапа

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

Көршілікті қайтару визуализаторы (NeRV)

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

Химия

Қашықтық матрицасы – химияның теориялық (топологиялық) және геометриялық (топографиялық) түрлерінде кеңінен қолданылатын математикалық объект. Химияда қашықтық матрицасы нақты және жасырын түрде қолданылады.

Екі пермутациялық изомерлердің өзара түрлендіру механизмдері

Қашықтық матрицалары екі пермутациялық изомерлердің арасындағы қайта орналасуды анықтауға қажетті ең қысқа жол тізбегін көрсету және анықтау үшін басты тәсіл ретінде қолданылды.

Қашықтық полиномиалдары мен қашықтық спектрлері

Алыстық матрицаларын тікелей пайдалану молекулалық құрылымдардың арақашықтық полиномдары мен арақашықтық спектрлерін құру үшін қажет.

Құрылым-мүліктілік модель

Қашықтық матрицаларын тікелей пайдалану, барлық химиялық құрылымдардағы қашықтықтарды көрсету үшін жасалған қашықтыққа негізделген Вайнер саны/Вайнер индексі арқылы жүзеге асты. Вайнер саны – қашықтық матрицасы элементтерінің қосындысының жартысына тең.

Графтық-теориялық қашықтық матрицасы

Химияда молекулалық графтарды 2D түрінде бейнелеу үшін қолданылатын қашықтық матрицасы, олар көптеген қолданбаларда молекуланың негізгі ерекшеліктерін көрсетуге мүмкіндік береді. Қашықтық матрицасына сүйене отырып, молекуланың көміртек қаңқасын көрсететін белгіленген ағаш құру. Бұл қолданбада қашықтық матрицасы маңызды, себебі ұқсас молекулалардың көміртек қаңқасының әртүрлі белгіленген ағаш түрлері болуы мүмкін. Мысалдағы қашықтық матрицасына негізделген гексанның (C6H14) көміртек қаңқасының белгіленген ағаш құрылымы, қашықтық матрицасына да, белгіленген ағашқа да әсер ететін әртүрлі көміртек қаңқасының нұсқаларын қамтиды. Химиялық графтар теориясында қолданылатын, гетероатомдары бар молекулаларды бейнелейтін, қабырға салмақтары бар белгіленген граф құру. Ле-Верье-Фадеев кадрлық әдісі (LVFF) – полициклді графтардағы графтың ортасын анықтау процесін жеделдетуге арналған компьютерлік әдіс. Дегенмен, LVFF кіріс ретінде диагональдық қашықтық матрицасын қажет етеді, оны Хаусхолдердің тридиагональдық QL алгоритмін іске асыру арқылы оңай шешуге болады, ол қашықтық матрицасын қабылдап, LVFF әдісі үшін қажетті диагональдық қашықтықты қайтарады.

Геометриялық қашықтық матрицасы

2D графиктік теориялық қашықтық матрицасы молекуланың құрылымдық ерекшеліктерін көрсетеді, ал оның үш өлшемді (3D) сипаттамасы геометриялық қашықтық матрицасында кодталған. Геометриялық қашықтық матрицасы – бұл 3D молекула құрылымын бейнелеу және графиктік түрде көрсету үшін молекуланың графиктік теориялық қашықтық матрицасына негізделген, қашықтық матрицасының басқа түрі. Молекулалық құрылымның геометриялық қашықтық матрицасы G – 2D матрицасы сияқты анықталатын, нақты симметриялық n x n матрица болып табылады. Дегенмен, матрица элементтері D<sub>ij</sub> i мен j арасындағы ең қысқа декарт қашықтықтарының жиынтығын қамтиды. Сондай-ақ топографиялық матрица деп аталатын геометриялық қашықтық матрицасын молекуланың белгілі геометриясынан құрастыруға болады. Мысал ретінде, 2,4 диметилгексанның көміртек қаңқасының геометриялық қашықтық матрицасы төменде көрсетілген:

Уақыт тізбесін талдау

Динамикалық уақыт бүліну қашықтық матрицалары уақыт сериясы объектілерінің жиынтығындағы/тобындағы кластерлеу және жіктеу алгоритмдерімен пайдаланылады.