Modelo de doble corte y unión

El modelo de doble corte y unión (DCJ) es un modelo de reordenamiento genómico que define una distancia de edición entre genomas basada en el orden y la orientación de los genes , en lugar de la secuencia de nucleótidos . Considera que las unidades fundamentales de un genoma son los bloques de sintenia , secciones máximas de ADN conservadas entre genomas. Se centra en los cambios debidos a operaciones de reordenamiento genómico, como inversiones , translocaciones , así como la creación y absorción de intermediarios circulares. ^{[ 1 ] [ 2 ]}

Un genoma se describe como un grafo dirigido con aristas etiquetadas, donde cada vértice tiene grado 1 o 2. Las aristas se etiquetan como bloques de sintenia, los vértices de grado 1 representan telómeros y los vértices de grado 2 representan adyacencias entre bloques. Esto requiere que el genoma consista en ciclos y caminos . Cada componente se llama cromosoma. El inicio de cada arista se llama cola, el final de cada arista se llama cabeza; juntas, cabezas y colas se conocen como extremos. Los vértices se describen por sus funciones como cabezas y colas de bloques; por ejemplo, en la figura, la adyacencia que forma la cabeza del marcador 1 y la cola del marcador 2 se etiqueta como (h1, t2), y el telómero formado por la cabeza de 2 es (h2). Una operación de doble corte y unión (DCJ) consiste en una de las siguientes cuatro transformaciones:

• (i) romper dos adyacencias (a, b) y (c, d) para crear dos adyacencias más, (a, c) y (b, d)
• (ii) tomar una adyacencia (a, b) y un telómero (c) para crear una nueva adyacencia y telómero, ya sea como (a, c), (b) o (b,c), (a).
• (iii) tomando dos telómeros (a) y (b) y creando una nueva adyacencia (a, b)
• (iv) romper una adyacencia (a, b) para crear los dos telómeros (a) y (b).

Se define una distancia de edición, la distancia de doble corte y unión, entre genomas con el mismo número de aristas.${\displaystyle G_{1}}$y${\displaystyle G_{2}}$,${\displaystyle d_{DCJ}(A,B)}$como el número mínimo de operaciones DCJ necesarias para transformar${\displaystyle A}$en${\displaystyle B}$.

La distancia DCJ define un espacio métrico . Para verificar esto, primero observamos que${\displaystyle d_{DCJ}(G,G)=0}$, puesto que no se necesitan operaciones para transformar G en sí mismo, y si${\displaystyle G_{1}\neq G_{2}}$,${\displaystyle d_{DCJ}(G_{1},G_{2})>0}$, ya que se necesita al menos una operación para transformar${\displaystyle G_{1}}$en cualquier otro genoma. (Una prueba de que el${\ Displaystyle d_ {DCJ} (G_ {1}, G_ {2})}$siempre se define cuando${\displaystyle G_{1}}$y${\displaystyle G_{2}}$son genomas con los mismos bordes seguirán.) Tenga en cuenta que cada operación tiene una inversa: (i) y (ii) son sus propias inversas, y (iii) es la inversa de (iv). Por lo tanto${\ Displaystyle d_ {DCJ} (G_ {1}, G_ {2}) = d_ {DCJ} (G_ {2}, G_ {1})}$La desigualdad triangular${\ Displaystyle d_ {DCJ} (G_ {1}, G_ {3}) \ leq d_ {DCJ} (G_ {1}, G_ {2}) + d_ {DCJ} (G_ {2}, G_ {3})}$se sostiene porque una serie de operaciones de DCJ transforman ${\displaystyle G_{1}}$a${\displaystyle G_{2}}$ seguido de una serie de transformaciones desde${\displaystyle G_{2}}$a${\displaystyle G_{3}}$se transformará${\displaystyle G_{1}}$a${\displaystyle G_{3}}$, por lo que el número mínimo de operaciones necesarias para transformar${\displaystyle G_{1}}$a${\displaystyle G_{3}}$No debe ser más largo que esto.

Para calcular la distancia DCJ entre dos genomas${\displaystyle G_{1}}$y${\displaystyle G_{2}}$Con el mismo conjunto de bloques de sintenia, construimos un multigrafo bipartito conocido como grafo de adyacencia.${\ Displaystyle A = (V (G_ {1}), V (G_ {2}), E)}$de los genomas. El conjunto de vértices del grafo de adyacencia es${\displaystyle (V(G_{1}),V(G_{2}))}$, dónde${\displaystyle V(G_{1})}$es el conjunto de vértices de${\displaystyle G_{1}}$y${\displaystyle V(G_{2})}$es el conjunto de vértices de${\displaystyle G_{2}}$. Para${\displaystyle a\in V(G_{1})}$y${\displaystyle b\in V(G_{2})}$, tenemos${\displaystyle (a,b)\in E}$si${\displaystyle a}$y${\displaystyle b}$son un extremo del mismo bloque de sintenia. Si${\displaystyle a}$y${\displaystyle b}$compartimos dos extremos, agregamos dos aristas entre${\displaystyle a}$y${\displaystyle b}$a${\displaystyle G}$.

Si${\displaystyle A=B}$, vemos que el grafo de adyacencia está compuesto enteramente por caminos de longitud 1, que conectan dos telómeros, y ciclos de longitud 2, que conectan dos adyacencias. Podemos usar este hecho para calcular${\displaystyle d_{DCJ}}$${\displaystyle }$. Dejar${\displaystyle N}$sea ​​el número de bloques de sintenia en los genomas${\displaystyle G_{1}}$y${\displaystyle G_{2}}$,${\displaystyle C}$sea ​​el número de ciclos en su grafo de adyacencia, y${\displaystyle I}$sea ​​el número de caminos en su grafo de adyacencia. Entonces${\displaystyle d_{DCJ}(G_{1},G_{2})=N-(C+1/2).}$La prueba muestra que cada operación DCJ puede disminuir${\displaystyle N-(C+1/2)}$por no más de 1, y que si${\displaystyle G_{1}\neq G_{2}}$, existe una operación decreciente${\displaystyle N-(C+I/2).}$Esto demuestra que${\displaystyle d_{DCJ}}$Siempre está definido y proporciona un método para su cálculo. Dado que es fácil contar ciclos y caminos,${\displaystyle d_{DCJ}}$se puede encontrar en tiempo lineal. ^{[ 3 ]}