Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Modelos para el estudio de ADN (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

Reconstruction: Definición
Dado un conjunto de strings F y una cota de error ? entre 0 y 1, hallar un string S de longitud mínima tal que para todo string f en F
donde f es el string reverso y complementario a f.

Monografias.com

Reconstruction: Resumen
No admite repeticiones ni espacios no cubiertos
Admite errores experimentales
Modela la orientación desconocida
Es un problema NP-Hard.
SCS es un caso particular de este modelo.

Monografias.com

Tercer Modelo:Multicontig:
Introduce la noción de buen enlace.
Este modelo tiene en cuenta:
Errores.
Orientación reconocida
Falta de cubrimiento
En algunos casos, repeticiones

Monografias.com

Multicontig: Definiciones
Llamaremos layout a un alineamiento múltiple de un conjunto de secuencias.
El siguiente layout será utilizado como ejemplo en varias definiciones:

Monografias.com

Multicontig: Definiciones (cont.)
Diremos que dos fragmentos f y g se solapan (y lo llamaremos overlap) si comparten una o más columnas en el layout. Es decir, si ambos string se intersecan.

Monografias.com

Multicontig: Definiciones (cont.)
Podemos separar los overlaps en dos categorías:
Los que producen un enlace. (f3 – f4)
y los que no lo producen. (f2 – f5)

Monografias.com

Multicontig: Definiciones (cont.)
El enlace más débil (weakest link) es aquél overlap con menor longitud que produce un enlace.
Diremos que un layout es un t-contig si el enlace más débil que posee tiene longitud t.
Si es posible obtener un t-contig de un conjunto de fragmentos F, diremos que F admite un t-contig.

Monografias.com

Multicontig: Definición ILibre de Errores
Dado un conjunto de strings F y un entero t, particionar F en el mínimo número de subconjuntos Ci, 1 = i = k, tal que cada Ci admita un t-contig.

Monografias.com

Multicontig: Ejemplos
Dado F = {GTAC, TAAG, TGTAA}

Monografias.com

Multicontig: Contemplando errores
Si se admiten errores en el acoplamiento, se debe obtener una cadena por consenso que será el resultado del ensamblamiento.
Diremos que S es una cadena ?-consensuada de F si, para cada cadena f en F, la distancia de edición entre f y su imagen en S es = | f |.

Monografias.com

Multicontig: Contemplando errores
Por ejemplo: S es una cadena 0.20 – consensuada con respecto a F.

Monografias.com

Multicontig: Definición IIAdmitiendo de Errores
Dado un conjunto de strings F, un entero t = 0 y una tolerancia de error ? entre 0 y 1, particionar F en el mínimo número de subconjuntos Ci, 1 = i = k, tal que cada Ci admita un t-contig con un consenso ?.

Monografias.com

Multicoting: Resumen
Admite repeticiones en algunos casos.
Admite errores experimentales
Modela la orientación desconocida
Es un problema NP-Hard.

Monografias.com

Repaso de Grafos
Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole.

Monografias.com

Repaso de Grafos
Un grafo simple está formado por dos conjuntos:
Un conjunto V de puntos llamados vértices o nodos.
Un conjunto E de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados.
Notación: G(V,E)
x
x
y

Monografias.com

Repaso de Grafos
A los ejes se les puede asignar un peso. Notación: w(x,y)
Si hay más de un arco hablamos de un multigrafo
Si los arcos se recorren en una en una dirección concreta pero no en la contraria lo llamamos grafo dirigido o dígrafo y los arcos son aristas
x
y
8
x
y
x
y
x
y

Monografias.com

Repaso de Grafos
Un Camino es una secuencia de vértices V1, V2, V3, … , Vn, tal que cada para uno de estos V1->V2, V2->V3, V1->V3
Un Camino Simple es cuando todos sus vértices, excepto tal vez el primero y el último son distintos.
Un Ciclo Simple es un camino simple de longitud por lo menos de uno que empieza y termina en el mismo vértice.
Se dice que un grafo es aciclíco cuando no contiene ciclos.
v1
v2
v3
v4
v1
v2
v3
v4
v1
v2
v3
v1
v2
v3

Monografias.com

Representado el problema como un grafo
Se representa con un grafo ya que resulta mas amigable para verlo visualmente, y se le esta aportando al problema, todo un conjunto de herramientas matemáticas para resolverlo.

Monografias.com

Representado el problema como un grafo
Datos del problema:
Un conjunto de fragmentos F F = {ACTT, TTGTAA, AAGGT, TTGT, GTT, TTAG}
Un string S S = ACTTGTAAGGTTGTTAAG
El overlap de los fragmentos ACTT TTGTAA

Monografias.com

Representado el problema como un grafo
Datos del problema:
El orden en que se hace el overlap ACTT TTGTAA TTGTAA ACTT
La cantidad de nucleotidos que están en el overlap ACTT TTGTAA 2 nucleótidos

Monografias.com

Representado el problema como un grafo
Fragmentos son representados por los nodos o vértices.
Los overlap’s son representados por los ejes que unen a los nodos.
El orden del overlap de dos fragmentos, esta dado por la dirección del eje o arista.
La cantidad de nucleótidos que estan en el overlap de dos fragmentos, esta representado por el peso de los ejes.
El string s se representa como un camino en el grafo.

Monografias.com

Representado el problema como un grafo
Ejemplo:
F={TACGA, ACCC, CTAAAG, GACA} a b c d
a
d
c
b
2
0
0
0
0
0
0
0
1
1
1
1

Monografias.com

Representado el problema como un grafo
Ejemplo:
F={TACGA, ACCC, CTAAAG, GACA} a b c d
a
d
c
b
2
1
1
1
1

Monografias.com

Representado el problema como un grafo
Ejemplo:
F={TACGA, ACCC, CTAAAG, GACA} a b c d

S1= TACGACCCCTAAAGACA
S2= TACGACACCCTAAAG
a
d
c
b
2
1
1
1
1
a
d
c
b
2
1
1
1
1

Monografias.com

Representado el problema como un grafo
Problema: Encontrar el superstring mas corto. Esto es equivalente a encontrar un camino hamiltoniano máximo dentro del grafo. Este problema es NP-Completo

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter