Herausfinden der RNA-Basenpaarung in gegebener Struktur

Question

Ich habe eine RNA-Sequenz, die so aussieht. Jedes Zeichen steht für eine Nukleotid (Programmierer dies ignorieren können, können Sie sie als Elemente behandeln):

  (((((((..((((.....(..)))).((((.........)))).....(((((..)....)))))))))))).... 

Ich werde diese Nomenklatur verwenden zum Zweck der Frage:

  (= lhb 
     ) = rhb 
      . = dot 

so wesentlichen Elemente mit LHB sind mit Elementen verbunden, die rhb haben, und alle Punkte sind freie Regionen. Die Art, wie sie verbunden sind, ist kompliziert. Es ist schwer in Worte zu fassen, so der Einfachheit halber werde ich Zahlen setzen unter einige der Elemente, die miteinander verbunden sind:

(((((((..((((.....(..)))).((((.........)))).....(((((..)....)))))))))))).... 
    1     2 2  3   3   45 5 4   1 

ich denke, das Sie geben eine Vorstellung davon, wie sie verbunden sind. Ich bin daran interessiert, die Standorte von verbundenen Elementen und freien Regionen herauszufinden.

(z. B. Element 1 ist mit Element 72 verbunden und Elemente 8 bis 9 sind frei).

I wählte C, um zu codieren, aber ich bin nicht wo nahe an Logik.

Auch wird es schwieriger, in C zu programmieren. Ich fühle, dass man dies leicht in Python mit regulären Ausdrücken machen kann oder Perl sein kann, aber ich habe nicht viel Erfahrung mit diesen Sprachen. Also, wenn jemand eine einfachere Methode zur Verfügung stellen kann, wird das eine große Hilfe sein. Ideen zur Verbesserung des C-Codes sind ebenfalls willkommen. Hier ist meine C-Code: -

#include <stdio.h> 

int main() { 

char dot[500]; 
int i = 0, j = 0; 
int count = 0, count1 = 0, count2 = 0; 
int lhb[100]; 
int rhb[100]; 
int dots[100]; 
int pair_1[100]; 
int pair_2[100]; 
int pair_3[100]; 
FILE * fp; 

fp = fopen("structure.txt", "r"); 

while (fscanf(fp, "%c", & dot[i]) != EOF) { 

    i++; 
} 

fclose(fp); 

for (i = 0; dot[i] != '\0'; i++) { 

    if (dot[i] == '(') { 
    lhb[count] = dot[i]; 
    pair_1[count] = i; 
    count++; 
    } 
    else if (dot[i] == '.') { 
    rhb[count1] = dot[i]; 
    pair_2[count1] = i; 
    count1++; 
    } 
    else { 
    dots[count2] = dot[i]; 
    pair_3[count2] = i; 
    count2++; 
    } 
} 


printf("Base-pair details :\n"); 

for (j = 0; j < count; j++) 

    printf("%d--%d\n", pair_1[j] + 1, pair_3[count - j - 1] + 1); 

printf("Loop details :\n"); 

// for(j=0;j<=count;j++) 

// printf("--%d-",pair_2[j]+1); 

return 0; 

} 

Answer 1

Ich bin mir nicht sicher, was Sie genau erhalten möchten, aber diese Perl erzeugt das gleiche wie Navidad20. Es beruht auf regulären Ausdrücken. Es verwendet das Regexp::Common Modul, um die Positionen der ausgeglichenen Klammern zu erhalten, und eine einfache while Schleife, um die Positionen der 'freien' Elemente zu erhalten. Es zählt beginnend bei 1, nicht bei 0 beginnend.

Ich weiß nicht, wie es sich mit ungültigen Daten verhalten würde.

#!/usr/bin/perl 
use strict; 
use warnings; 
use Regexp::Common qw /balanced/; 

my $seq = '(((((((..((((.....(..)))).((((.........)))).....(((((..)....))))))))))))....'; 

while ($seq =~ /(?=($RE{balanced}{-parens=>'()'}))/g) { 
    print 1 + $-[1], ' ', $+[1], " $1\n"; 
} 

my @free; 
push @free, [ 1 + $-[0] .. $+[0] ] while $seq =~ /\.+/g; 

use Data::Dumper; print Dumper \@free; 

Ausgang ist:

1 72 (((((((..((((.....(..)))).((((.........)))).....(((((..)....)))))))))))) 
2 71 ((((((..((((.....(..)))).((((.........)))).....(((((..)....))))))))))) 
3 70 (((((..((((.....(..)))).((((.........)))).....(((((..)....)))))))))) 
4 69 ((((..((((.....(..)))).((((.........)))).....(((((..)....))))))))) 
5 68 (((..((((.....(..)))).((((.........)))).....(((((..)....)))))))) 
6 67 ((..((((.....(..)))).((((.........)))).....(((((..)....))))))) 
7 66 (..((((.....(..)))).((((.........)))).....(((((..)....)))))) 
10 65 ((((.....(..)))).((((.........)))).....(((((..)....))))) 
11 25 (((.....(..)))) 
12 24 ((.....(..))) 
13 23 (.....(..)) 
19 22 (..) 
27 43 ((((.........)))) 
28 42 (((.........))) 
29 41 ((.........)) 
30 40 (.........) 
49 64 (((((..)....)))) 
50 63 ((((..)....))) 
51 62 (((..)....)) 
52 61 ((..)....) 
53 56 (..) 
$VAR1 = [ 
      [ 
      8, 
      9 
      ], 
      [ 
      14, 
      15, 
      16, 
      17, 
      18 
      ], 
      [ 
      20, 
      21 
      ], 
      [ 
      26 
      ], 
      [ 
      31, 
      32, 
      33, 
      34, 
      35, 
      36, 
      37, 
      38, 
      39 
      ], 
      [ 
      44, 
      45, 
      46, 
      47, 
      48 
      ], 
      [ 
      54, 
      55 
      ], 
      [ 
      57, 
      58, 
      59, 
      60 
      ], 
      [ 
      73, 
      74, 
      75, 
      76 
      ] 
     ]; 

Answer 2

Hier ist eine mögliche Lösung. Free enthält eine Liste, die jeden Punkt indiziert, und Paare enthält eine Liste von Tupeln mit den Indizes jedes Paares. Dies basiert auf der Annahme, dass Ihre Daten perfekt sind (d. h. die gleiche Anzahl von linken und rechten Paaren, keine rechten Paare vor linken Paaren). Dies kann jedoch geändert werden, um nach Kantenfällen zu suchen. Auf der Grundlage Ihrer Frage begann ich den Index bei 1 statt 0.

data = '(((((((..((((.....(..)))).((((.........)))).....(((((..)....))))))))))))....' 

left = [] 
group = [] 
prev = '' 

free = [] 
pairs = [] 

for index, elem in enumerate(data, 1): 
    if elem == '.' and prev == '.': 
     group.append(index) 
    elif elem == '.': 
     group = [index] 
    else: 
     if len(group) >= 1: 
      free.append(group) 
      group = [] 
     if elem == '(': 
      left.append(index) 
     elif elem == ')': 
      pairs.append([left.pop(), index]) 
    prev = elem 
if len(group) > 0: 
    free.append(group) 
pairs.sort() 

Ausgang:

[[1, 72], [2, 71], [3, 70], [4, 69], [5, 68], [6, 67], [7, 66], [10, 65], [11, 25], [12, 24], [13, 23], [19, 22], [27, 43], [28, 42], [29, 41], [30, 40], [49, 64], [50, 63], [51, 62], [52, 61], [53, 56]] 
[[8, 9], [14, 15, 16, 17, 18], [20, 21], [26], [31, 32, 33, 34, 35, 36, 37, 38, 39], [44, 45, 46, 47, 48], [54, 55], [57, 58, 59, 60]] 

Der Code funktioniert, indem Sie einmal über jedes Element laufen. Wenn es auf ein linkes Argument trifft, hängt es den Index an eine Liste an. Wenn es dann auf einen rechten Paren stößt, springt es aus dem Index des zuletzt gesehenen linken Parens und erzeugt ein Paar. Was die freien Punkte betrifft, zeigt Ihnen die Verfolgung des vorherigen Elements, wie Sie mit jedem Punkt umgehen. Wenn eines gesehen wurde, fügen Sie der aktuellen Liste weitere hinzu, andernfalls starten Sie eine neue Liste.

Answer 3

Der beste Weg, um eine solche Frage wirklich zu lösen, ist die Wartung eines Stapels. Für jede (, die aufgetreten ist, können Sie den Indexwert in den Stapel schieben und für jede ) müssen Sie den Stapel mit der Nummer, wo der letzte ( Index eingefügt wurde. Dies bedeutet, dass der Index der ( und der der ) ein Paar bildet.

Dies kann etwas zu tun, wie diese

seq = '(((((((..((((.....(..)))).((((.........)))).....(((((..)....))))))))))))....' 
xStack = [] 
for i, x in enumerate(seq): 
    if x == '(': 
     xStack.append(i) 
    if x == ')': 
     o = xStack.pop() 

nun mit den grundlegenden Schritten statt, es gibt ein paar Dinge, die Sie müssen zusammen mit Beibehaltung des Index der Klammer erreicht werden.Nach dem Pop-Operation Sie das passende Paar zu speichern brauchen würde, dies zu tun, können andere Variable einführen und im Grunde nichts zu tun, wenn wir die .

seq = '(((((((..((((.....(..)))).((((.........)))).....(((((..)....))))))))))))....' 

xStack = [] 

resultingPairs = [] 

for i, x in enumerate(seq): 
    if x == '(': 
     xStack.append(i) 
    if x == ')': 
     o = xStack.pop() 
     tempPair = [o, i] 
     resultingPairs.append(tempPair) 
    if x == '.': 
     pass 

Jetzt begegnen, dass wir die resultierenden Paare haben, die wie dieses aussehen

[[18, 21], [12, 22], [11, 23], [10, 24], [29, 39], [28, 40], [27, 41], [26, 42], [52, 55], [51, 60], [50, 61], [49, 62], [48, 63], [9, 64], [6, 65], [5, 66], [4, 67], [3, 68], [2, 69], [1, 70], [0, 71]] 

müssen wir herausfinden, wo alle Freiräume, kann dies leicht, indem sie als

spacesList = [i for i in range(len(seq)) if seq.startswith('.', i)] 

folgt tun etwas getan werden whic h ergibt

[7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59, 72, 73, 74, 75] 

können Sie jetzt schreiben einfach eine Funktion, wo Sie die spacesList und die resultingPairs passieren und die Anzahl der freien Räume zwischen jedem möglichen Paar bekommen. Es sind viele Optimierungen möglich, aber dies sollte Ihnen den Einstieg in die richtige Richtung ermöglichen.

und Sie haben die Werte der Position der öffnenden Klammer, schließenden Klammern und die Anzahl der freien Leerzeichen zwischen ihnen.

>>> getSpacesCount(spacesList, resultingPairs) 
18 21 2 
12 22 7 
11 23 7 
10 24 7 
29 39 9 
28 40 9 
27 41 9 
26 42 9 
52 55 2 
51 60 6 
50 61 6 
49 62 6 
48 63 6 
9 64 28 
6 65 30 
5 66 30 
4 67 30 
3 68 30 
2 69 30 
1 70 30 
0 71 30 

bearbeiten Kann nicht scheinen, um herauszufinden, wie Stackoverflow Kommentare, aktualisieren Sie die Funktion

def getSpacesCount(spacesList, resultingPairs): 
    for pair in resultingPairs: 
     a = pair[0] 
     b = pair[1] 
     spacesCount = 0 
     spaces = [] 
     for val in spacesList: 
      if a < val < b: 
       spaces.append(val) 
       spacesCount+=1 
     print a,b,spacesCount,spaces 

Diese Sie Zahl und Positionen sowohl bearbeiten geben. Sie können das behalten, was Sie wirklich mögen.

>>> getSpacesCount(spacesList, resultingPairs) 
18 21 2 [19, 20] 
12 22 7 [13, 14, 15, 16, 17, 19, 20] 
11 23 7 [13, 14, 15, 16, 17, 19, 20] 
10 24 7 [13, 14, 15, 16, 17, 19, 20] 
29 39 9 [30, 31, 32, 33, 34, 35, 36, 37, 38] 
28 40 9 [30, 31, 32, 33, 34, 35, 36, 37, 38] 
27 41 9 [30, 31, 32, 33, 34, 35, 36, 37, 38] 
26 42 9 [30, 31, 32, 33, 34, 35, 36, 37, 38] 
52 55 2 [53, 54] 
51 60 6 [53, 54, 56, 57, 58, 59] 
50 61 6 [53, 54, 56, 57, 58, 59] 
49 62 6 [53, 54, 56, 57, 58, 59] 
48 63 6 [53, 54, 56, 57, 58, 59] 
9 64 28 [13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59] 
6 65 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59] 
5 66 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59] 
4 67 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59] 
3 68 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59] 
2 69 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59] 
1 70 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59] 
0 71 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59]