Naukowcy z Cold Spring Harbor Laboratory (CSHL) odkryli zaskakujący związek między procesem rozwoju układu nerwowego a klasycznym problemem informatyki znanym jako maksymalne skojarzenie w grafach dwudzielnych. Prof. Saket Navlakha zauważył, że sposób, w jaki neurony konkurują o tworzenie połączeń z włóknami mięśniowymi w ciele, może informować o bardziej wydajnych algorytmach do łączenia kierowców z pasażerami, dawców organów z kandydatami do przeszczepu i reklamodawców z miejscami reklamowymi.
Czytaj też: Matematyka królową nauk i całej przyrody. Znaleziono odpowiedź na bardzo ważne pytanie
To może doprowadzić do skrócenia czasu oczekiwania na zamówiony przejazd, mniejszej liczby niedopasowanych stron, a nawet zachowania prywatności w transakcjach online. Algorytm inspirowany neuronauką, który został przetestowany w porównaniu z najlepszymi programami skojarzenia w grafach dwudzielnych, działa wyjątkowo dobrze i ma dalekosiężne potencjalne zastosowania. Szczegóły opisano w czasopiśmie PNAS.
Algorytm inspirowany neuronami
Gdy prosimy aplikację do współdzielenia przejazdów o znalezienie samochodu, komputery firmy zabierają się do pracy. Wiedzą, że chcemy szybko dotrzeć do celu. Wiedzą, że nie jesteśmy jedynymi, którzy potrzebuje transportu. I wiedzą, że kierowcy chcą zminimalizować czas przestoju, zabierając kogoś w pobliżu. Zadaniem komputera jest łączenie kierowców z pasażerami w sposób, który maksymalizuje zadowolenie wszystkich. To przykład tzw. maksymalnego skojarzenia w grafach dwudzielnych.
Czytaj też: To matematyka steruje biologią! Coraz bliżej odkrycia największej tajemnicy życia
Jest to podstawowy problem informatyki, w którym celem jest optymalne sparowanie dwóch zestawów jednostek. Problem ten pojawia się w różnych zastosowaniach, takich jak usługi współdzielonych przejazdów, dopasowywanie dawców narządów i programy rezydentury dla studentów medycyny. Informatycy intensywnie badają ten problem, a prof. Saket Navlakha wniósł znaczący wkład w tę dziedzinę na podstawie obserwacji układów biologicznych.
U dorosłych zwierząt każde z włókien mięśniowych ciała jest sparowane z dokładnie jednym neuronem, który kontroluje jego ruch. Jednak na wczesnym etapie życia każde włókno jest celem wielu neuronów. Aby zwierzę poruszało się wydajnie, należy przyciąć nadmiarowe połączenia (tzw. przycinanie rozwojowe). Jak organizm tego dokonuje?
Okazuje się, że wyjaśnia, że neurony początkowo połączone z tym samym włóknem mięśniowym konkurują ze sobą, aby utrzymać swoje dopasowanie, wykorzystując neuroprzekaźniki jako zasoby “licytacyjne”. Neurony, które przegrywają tę biologiczną aukcję, mogą zabrać swoje neuroprzekaźniki i licytować się na inne włókna. W ten sposób każdy neuron i włókno ostatecznie kończy z partnerem.
Prof. Navlakha opracował prosty algorytm oparty na strategii układu nerwowego, który składa się z dwóch równań: jednego dla konkurencji między neuronami podłączonymi do tego samego włókna i drugiego dla realokacji zasobów. Ten zainspirowany neuronauką algorytm został przetestowany w oparciu o istniejące programy skojarzenia w grafach dwudzielnych i działa niezwykle dobrze, tworząc niemal optymalne pary i pozostawiając mniej stron bez dopasowania.
Co ciekawe, algorytm oferuje kilka zalet w porównaniu z tradycyjnymi podejściami. Chroni prywatność, ponieważ nie wymaga centralnego serwera do przetwarzania informacji, dzięki czemu nadaje się do zastosowań, w których preferowane jest przetwarzanie rozproszone. Ponadto wydajność algorytmu może prowadzić do krótszego czasu oczekiwania pasażerów współdzielonych przejazdów i mniejszej liczby szpitali bez rezydentów medycznych. Ta praca pokazuje siłę współpracy między biologami a informatykami w celu opracowywania innowacyjnych rozwiązań inspirowanych naturą.