Algoritmo ayuda! Algoritmo rápido en la búsqueda de una cadena con su compañero

Question

Estoy buscando un algoritmo rápido para fines de búsqueda en una cadena enorme (es una secuencia del genoma del organismo compuesta de cientos de millones a miles de millones de caracteres).

Hay solo 4 caracteres {A, C, G, T} presentes en esta cadena, y "A" solo puede emparejarse con "T" mientras que "C" se empareja con "G".

Ahora estoy buscando dos subcadenas (con la restricción de longitud de ambas subcadenas entre {minLen, maxLen}, y la duración del intervalo entre {intervalMinLen, intervalMaxLen}) que pueden vincularse entre sí de forma antiparalela.

Por ejemplo, La cadena es: ATCAG Gacca TACGC CTGAT

restricciones: minlen = 4, maxlen = 5, intervalMinLen = 9, intervalMaxLen = 10

El resultado debe ser

1. par "ATCAG" con "CTGAT"

2. "TCAG" par con "CTGA"

Gracias de antemano.

Actualización: Ya tengo el método para determinar si dos cadenas se pueden emparejar entre sí. La única preocupación es hacer una búsqueda exhaustiva que consume mucho tiempo.

Answer 1

pensé que esto era un problema interesante, por lo que poner juntos un programa basado en la consideración de 'pliegues', que escanea hacia afuera para su posible coincidencias simétricas de diferentes 'puntos de plegado'. Si N es el número de nucleótidos y M es 'maxInterval-minInterval', debe tener un tiempo de ejecución O (N * M). Es posible que haya pasado por alto algunos casos límite, así que use el código con cuidado, pero funciona para el ejemplo proporcionado. Tenga en cuenta que he utilizado un buffer intermedio acolchado para almacenar el genoma, ya que esto reduce el número de comparaciones para casos límite requeridos en los bucles internos; esto intercambia la asignación de memoria adicional para una mejor velocidad. Siéntase libre de editar la publicación si realiza alguna corrección o mejora.

class Program 
{ 
    public sealed class Pairing 
    { 
     public int Index { get; private set; } 

     public int Length { get; private set; } 

     public int Offset { get; private set; } 

     public Pairing(int index, int length, int offset) 
     { 
      Index = index; 
      Length = length; 
      Offset = offset; 
     } 
    } 

    public static IEnumerable<Pairing> FindPairings(string genome, int minLen, int maxLen, int intervalMinLen, int intervalMaxLen) 
    { 
     int n = genome.Length; 
     var padding = new string((char)0, maxLen); 
     var padded = string.Concat(padding, genome, padding); 

     int start = (intervalMinLen + minLen)/2 + maxLen; 
     int end = n - (intervalMinLen + minLen)/2 + maxLen; 

     //Consider 'fold locations' along the genome 
     for (int i=start; i<end; i++) 
     { 
      //Consider 'odd' folding (centered on index) about index i 
      int k = (intervalMinLen+2)/2; 
      int maxK = (intervalMaxLen + 2)/2; 
      while (k<=maxK) 
      { 
       int matchLength = 0; 
       while (IsPaired(padded[i - k], padded[i + k]) && (k <= (maxK+maxLen))) 
       { 
        matchLength++; 

        if (matchLength >= minLen && matchLength <= maxLen) 
        { 
         yield return new Pairing(i-k - maxLen, matchLength, 2*k - (matchLength-1)); 
        } 
        k++; 
       } 
       k++; 
      } 

      //Consider 'even' folding (centered before index) about index i 
      k = (intervalMinLen+1)/2; 
      while (k <= maxK) 
      { 
       int matchLength = 0; 
       while (IsPaired(padded[i - (k+1)], padded[i + k]) && (k<=maxK+maxLen)) 
       { 
        matchLength++; 

        if (matchLength >= minLen && matchLength <= maxLen) 
        { 
         yield return new Pairing(i - (k+1) - maxLen, matchLength, 2*k + 1 - (matchLength-1)); 
        } 
        k++; 
       } 
       k++; 
      } 
     } 
    } 

    private const int SumAT = 'A' + 'T'; 
    private const int SumGC = 'G' + 'C'; 
    private static bool IsPaired(char a, char b) 
    { 
     return (a + b) == SumAT || (a + b) == SumGC; 
    } 


    static void Main(string[] args) 
    { 
     string genome = "ATCAGGACCATACGCCTGAT"; 
     foreach (var pairing in FindPairings(genome, 4, 5, 9, 10)) 
     { 
      Console.WriteLine("'{0}' pair with '{1}'", 
           genome.Substring(pairing.Index, pairing.Length), 
           genome.Substring(pairing.Index + pairing.Offset, pairing.Length)); 
     } 
     Console.ReadKey(); 
    } 


} 

Answer 2

La solución más fácil sería construir un Trie a partir de los datos de altura máxima maxLen. Cada nodo también debe tener una lista de ubicaciones donde se encontró esa cadena en particular (estará en orden ascendente, si el trie se crea en orden).

Luego, mientras busca, simplemente haga doble clic en la cadena de búsqueda y vaya a través del trie. Cuando encuentre una verificación de coincidencia si una de las coincidencias se encuentra en el intervalo adecuado, si la respuesta es "sí", envíe las cadenas.

Avíseme si necesita el algoritmo detallado.

Answer 3

me gustaría considerar la conversión de las cuerdas a binario en 16 longitudes de bits:

A = 101
T = 010
C = 110
G = 001

Esto permite hasta 5 caracteres por unidad de 16 bits. Esto debería ser muy rápido en comparación con las búsquedas y comparaciones de cadenas.

Utilice la parte superior para determinar si se trata de una unidad de secuencia de 4 o 5 unidades de secuencia.

Ahora puede hacer una ordenación rápida y obtener todas las 4 unidades de secuencia y 5 en sus propios grupos (a menos que necesite encontrar 4 unidades de secuencia que coincidan parcialmente con 5 unidades de secuencia).

Para la comparación puede ordenar de nuevo, y encontrará que todas las secuencias que comienzan con G aparecerán antes de las secuencias que comienzan con T, luego A y C. Luego puede tomar una secuencia y compararla solo las partes de la matriz ordenada que son posibles, que deberían ser un espacio problemático mucho, mucho más corto.

Además, la razón por la que he elegido esas codificaciones de tres bits para las secuencias es que simplemente puede conectar las dos cadenas para ver si coinciden. Si obtienes 15 1 en secuencia, entonces los dos coinciden perfectamente. Si no, entonces no lo hacen.

Tendrá que descubrir la broca antiparalela, tengo algunas ideas al respecto, pero esto debería comenzar, y si la parte anular-paralela se convierte en un problema, haga otra pregunta.

Answer 4

Sé que no está buscando subcadenas, pero creo que valdría la pena crear una cadena de genoma invertida que contenga las coincidencias; la tarea sería encontrar subcadenas comunes en las dos cadenas.

Ejemplo:

cadena original

ATCAG GACCA TACGC CTGAT 

cadena Invertida:

TAGTC CGCAT ACCAG GACTA 

Si a continuación transformar la cadena que es valores emparejamiento (reemplace T < -> A y C < - > G, obtienes algo útil:

ATCAG GCGTA TGGTC CTGAT 

Sé que este preprocesamiento será costoso y consumirá mucho espacio, pero después podrá utilizar algoritmos de cadenas estándar y con la cantidad de comparaciones que está buscando, sin duda se justificará.

Cuando la cadena original y la cadena de búsqueda inversa creo que su problema suena sorprendentemente similar al problema 'longest common substring' que está bien descrito. Su segundo preprocesamiento sería construir un árbol de sufijos para permitir una búsqueda rápida de subcadenas.

puede acabar con tiempos de funcionamiento de segundo grado, pero dudo que se puede hacer mejor

Answer 5

El método se describe en http://www.ncbi.nlm.nih.gov/pubmed/11381028

Genome Res. 2001 Jun; 11 (6): 1005-17. Duplicaciones segmentadas: organización e impacto dentro del proyecto del genoma humano actual ensamblaje.