Wie finden Sie den ersten Index mehrerer 'Motive' in einer Sequenz?

Question

Ich lerne Julia, aber habe relativ wenig Programmiererfahrung außerhalb von R. Ich nehme dieses Problem direkt von rosalind.info und Sie können es here finden, wenn Sie ein bisschen mehr Details möchten.

Ich habe zwei Strings angegeben: ein Motiv und eine Sequenz, wobei das Motiv ein Teilstring der Sequenz ist und ich den Index der Anfangsposition des Teilstrings herausfinden soll, egal wie oft er in der Sequenz.

Zum Beispiel:

Sequenz: "GATATATGCATATACTT"

Motiv: "ATAT"

ATAT dreimal gefunden wird, einmal am Index beginnend 2, einmal an der Stelle 4 und einmal im Index 10. Dies setzt eine 1-basierte Indexierung voraus. So würde die endgültige Ausgabe sein:

Hier ist, was ich bisher:

f = open("motifs.txt") 
stream = readlines(f) 

sequence = chomp(stream[1]) 
motif = chomp(stream[2]) 

println("Sequence: $sequence") 
println("Motif: $motif") 

result = searchindex(sequence, motif) 
println("$result") 

close(f) 

Mein Hauptproblem scheint zu sein, dass es keine searchindexall Option. Das aktuelle Skript gibt mir den ersten Index des ersten Mal, wenn das Motiv gefunden wird (Index 2), ich habe eine Vielzahl von for-Schleifen ausprobiert, die nicht zu viel Erfolg haben, also hoffe ich, dass jemand mir einen Einblick geben kann darauf.

Answer 1

Hier ist eine Lösung mit While-Schleifen:

sequence = "GATATATGCATATACTT" 
motif = "ATAT" 

function find_indices(sequence, motif) 
    # initalise empty array of integers 
    found_indices = Array{Int, 1}() 

    # set initial values for search helpers 
    start_at = 1 

    while true 
     # search string for occurrence of motif 
     result = searchindex(sequence, motif, start_at) 

     # if motif not found, terminate while loop 
     result == 0 && break 

     # add new index to results 
     push!(found_indices, result-1+start_at) 
     start_at += result + 1 
    end 

    return found_indices 
end 

Das gibt, was Sie wollen:

>find_indices(sequence, motif) 
2 
4 
10 

Answer 2

Wenn die Leistung nicht so wichtig ist, kann regulärer Ausdruck eine gute Wahl sein.

julia> map(x->x.offset, eachmatch(r"ATAT", "GATATATGCATATACTT", true)) 
3-element Array{Any,1}: 
    2 
    4 
10 

PS. Das dritte Argument von eachmatch bedeutet "Überlappung", vergessen Sie nicht, es wahr zu setzen.

Wenn eine bessere Leistung erforderlich ist, sollten Sie vielleicht etwas Zeit mit der Implementierung eines Algorithmus wie KMP verbringen.