Przegrupowanie genomów
Zdarzenie rearanżacji genomu jest elementem dynamiki genomu, podczas którego genom widzi swoją ogólną organizację zmodyfikowaną przez przemieszczenie, delecję lub duplikację części jego sekwencji . Przegrupowania genomu obejmują między innymi:
- w tej samej cząsteczce DNA:
- odwrócenie sekwencji;
- delecje jednej lub więcej sekwencji DNA;
- utrata ramienia chromosomu;
- duplikacje sekwencji;
- między różnymi cząsteczkami DNA:
- duplikacja chromosomów;
- utrata chromosomu;
- połączenie dwóch chromosomów na ich końcach;
- translokacja między dwoma chromosomami.
Analiza rearanżacji chromosomów między gatunkami
Problem rearanżacji genomów jest problemem biologii, który można określić następująco: mając dwa genomy , znaleźć minimalną liczbę mutacji przekształcających jedną w drugą. Było to pod koniec 1980 roku , że Jeffrey Palmer i jego współpracownicy odkryli, że organizmy bardzo podobne pod względem genów oni akcje mogłyby mimo silnie rozchodzą się w kolejności, w jakiej te geny zostały ustawione.
Ten problem był również badany przez matematyków i informatyków przez około piętnaście lat. Wśród najbardziej płodnych pionierów i badaczy w tej dziedzinie niewątpliwie możemy wymienić Davida Sankoffa , Vineeta Bafnę , Sridhara Hannenhalliego i Pavla Pevznera . Wiele pozostaje do zrobienia, a badania naturalnie rozpoczęły się od zbadania ograniczonych form problemu, zwłaszcza w przypadku, gdy zakłada się, że może wystąpić tylko jeden typ mutacji. Badane mutacje to między innymi:
- złamania chromosomów ;
- na odwrócenie ;
- te skreślenia ;
- na przenoszenie ;
- na transpozycje ;
- fuzje;
- rozszczepienia.
Jak również w niektórych przypadkach kombinacja, prawdopodobnie ważona, dwóch lub trzech z tych mutacji.
Proponowane modele
W zależności od przypadku, w którym się znajdujemy, zaproponowano kilka modeli :
- jeśli kolejność genów jest znana, a badane genomy mają tę samą liczbę i zestaw genów bez duplikacji, można je przedstawić za pomocą permutacji, a problem rearanżacji sprowadza się do obliczenia odległości między permutacjami. Przynajmniej w przypadku inwersji i transpozycji odległości w ten sposób zdefiniowane są niezmienne po lewej stronie, tj. Obliczenie odległości między permutacją a permutacją jest takie samo, jak obliczenie odległości między permutacją a permutacją. Tożsamość permutacji; stąd pomysł powrotu do problemu sortowania permutacji według minimalnej liczby operacji, których typ ustaliliśmy. Na marginesie należy zauważyć, że sortowanie przez inwersje jest NP-trudne , a złożoność sortowania według transpozycji jest nieznana;
- jeśli znajdziemy się w powyższym przypadku, ale zdecydujemy się również wziąć pod uwagę orientację genów, modelujemy genomy przez podpisane permutacje, to znaczy zamiast rozważać permutacje {1, 2, ..., n}, rozważamy permutacje {± 1, ± 2, ..., ± n}. Godnym uwagi przykładem w tym przypadku jest sortowanie przez inwersje, których złożoność staje się wielomianowa w przypadku ze znakiem, podczas gdy w przypadku bez znaku była NP-trudna;
- jeśli znane są wszystkie geny, ale nie ich kolejność, możesz użyć reprezentacji zestawu: genomy są postrzegane jako nieuporządkowane zestawy chromosomów , które z kolei są zestawami nieuporządkowanych genów. To nie jest zgodne z rzeczywistością: chociaż prawdą jest, że chromosomy nie są uporządkowane w genomie, geny są zawsze uporządkowane na chromosomie. Jedną z odległości użytych w tym modelowaniu jest odległość syntenii (dwa geny są w syntenii, jeśli znajdują się na tym samym chromosomie), która wykorzystuje operacje fuzji, rozszczepienia i translokacji. Ten problem jest również NP-trudny.
