Algoritmo aiuto! Algoritmo veloce nella ricerca di una stringa con il suo partner

Question

Sto cercando un algoritmo veloce per scopi di ricerca in una stringa enorme (si tratta di una sequenza di genomi di organismi composta da centinaia di milioni a miliardi di caratteri).

Ci sono solo 4 caratteri {A, C, G, T} presenti in questa stringa, e "A" può solo accoppiarsi con "T" mentre "C" fa coppia con "G".

Ora sto cercando due sottostringhe (con limite di lunghezza sia della sottostringa tra {minLen, maxLen}, sia della lunghezza dell'intervallo tra {intervalMinLen, intervalMaxLen}) che possono accoppiarsi l'un l'altro in modo antiparallelo.

Ad esempio, La stringa è: ATCAG GACCA TACGC CTGAT

Vincoli: minLen = 4, MAXLEN = 5, intervalMinLen = 9, intervalMaxLen = 10

Il risultato dovrebbe essere

1. pair "ATCAG" con "CTGAT"

2. coppia "TCAG" con "CTGA"

Grazie in anticipo.

Aggiornamento: ho già il metodo per determinare se due stringhe possono accoppiarsi l'una con l'altra. L'unica preoccupazione è fare una ricerca esauriente richiede molto tempo.

Answer 1

ho pensato che questo fosse un problema interessante, così ho messo insieme un programma basato sul considerando 'pieghe', per la ricerca verso l'esterno per un eventuale partite simmetriche da diversi "punti di piega". Se N è il numero di nucleotidi e M è 'maxInterval-minInterval', si dovrebbe avere il tempo di esecuzione O (N * M). Potrei aver perso alcuni casi limite, quindi usa il codice con attenzione, ma funziona per l'esempio fornito. Si noti che ho usato un buffer intermedio imbottito per memorizzare il genoma, in quanto riduce il numero di confronti per i casi limite richiesti nei loop interni; questo scambia l'allocazione di memoria aggiuntiva per una migliore velocità. Sentiti libero di modificare il post se fai correzioni o miglioramenti.

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 soluzione più semplice sarebbe quella di costruire un Trie dai dati di altezza massima maxLen. Ogni nodo dovrebbe anche avere un elenco di posizioni in cui è stata trovata quella stringa particolare (sarà in ordine ascendente, se il trie viene creato in ordine).

Quindi, durante la ricerca, basta invertire complimentare la stringa di ricerca e passare attraverso il trie. Quando trovi una corrispondenza controlla se una delle corrispondenze si trova nell'intervallo corretto, se "sì" emette le stringhe.

Fammi sapere se è necessario l'algoritmo dettagliato.

Answer 3

mi piacerebbe prendere in considerazione la conversione delle stringhe a binario a 16 bit lunghezze:

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

Questo consente fino a 5 caratteri per unità da 16 bit. Questo dovrebbe essere molto veloce rispetto alle ricerche e ai confronti delle stringhe.

Utilizzare il bit superiore per determinare se si tratta di un'unità a 4 sequenze o 5 unità di sequenza.

Ora è possibile eseguire un ordinamento rapido e ottenere tutte le 4 sequenze e 5 unità di sequenza nei propri gruppi (a meno che non sia necessario trovare 4 unità di sequenza che corrispondono parzialmente a 5 unità di sequenza).

Per il confronto è possibile ordinare nuovamente, e scoprirai che tutte le sequenze che iniziano con G verranno prima delle sequenze che iniziano con T, quindi A e C. Puoi quindi prendere una sequenza e confrontarla con solo le parti dell'array ordinato che sono possibili, il che dovrebbe essere uno spazio di problemi molto più breve.

Inoltre, il motivo per cui ho scelto queste codifiche a tre bit per le sequenze è che puoi semplicemente xorare le due stringhe insieme per vedere se corrispondono. Se ottieni 15 1 in sequenza, i due corrispondono perfettamente. Se no, allora non lo fanno.

Dovrai capire il bit antiparallelo - Ho qualche idea su questo, ma questo dovrebbe farti iniziare, e se la parte anit-parallela diventa un problema, fai un'altra domanda.

Answer 4

So che non si cercano sottostringhe, ma penso che valga la pena creare una stringa di genoma invertita contenente le corrispondenze; il compito sarebbe quindi quello di trovare sottostringhe comuni nelle due stringhe.

Esempio:

stringa originale

ATCAG GACCA TACGC CTGAT 

stringa inversa:

TAGTC CGCAT ACCAG GACTA 

Se poi trasformare la stringa per i suoi valori di abbinamento (sostituire T < -> A e C < - > G, ottieni qualcosa di utile:

ATCAG GCGTA TGGTC CTGAT 

So che questa pre-elaborazione sarà costosa e consumerà molto spazio, ma dopo sarete in grado di utilizzare algoritmi di stringhe standard e con la quantità di confronti che state cercando, sarà sicuramente solo fatto.

Quando la stringa originale e la stringa di ricerca invertita Credo che il problema suona sorprendentemente simile al 'longest common substring' problema che è ben descritto. La seconda preelaborazione sarebbe quella di costruire un albero suffisso per consentire una rapida ricerca delle sottostringhe.

si finirà con tempi di esecuzione di secondo grado, ma dubito si può fare meglio

Answer 5

Il metodo è descritto in http://www.ncbi.nlm.nih.gov/pubmed/11381028

Genome Res. 2001 Jun; 11 (6): 1005-17. Duplicazione segmentale: organizzazione e impatto all'interno dell'attuale progetto del genoma umano assemblaggio.