Bir sıradaki çoklu 'motiflerin' ilk endeksini nasıl buluyorsunuz?

Question

Julia'yı öğreniyorum, fakat R dışında nispeten az programlama deneyimi var. Bu sorunu doğrudan rosalind.info'dan alıyorum ve biraz daha fazla ayrıntı istiyorsanız here'u bulabilirsiniz.

İki dizeyi verdim: bir motif ve dizinin dizinin bir alt dizesi olduğu bir sıra ve alt dizenin başlangıç ​​konumunun dizinini bulmakla görevlendirildim, ancak birçok kez sıra. Örneğin

:

Sıra: "GATATATGCATATACTT"

Motif: "ATAT"

ATAT endeksinde seferde bir kez bir kez indeksi 4'te, endeks 2 başlayarak, üç kez bulundu ve edilir 10. Bu, 1 tabanlı endeksleme varsayılmaktadır. Yani son çıkış olacaktır:

İşte ben bugüne kadar ne var:

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) 

Benim asıl sorun searchindexall seçenek olmadığını gibi görünüyor. Mevcut betik bana, motifin karşılaştığı ilk zamanın ilk indeksini verir (index 2), çok fazla başarı göstermeyen döngüler için çeşitli denemeler yaptım, böylece birinin bana biraz bilgi vermesini umuyordum bu konuda.

Answer 1

Burada süre ile bir çözüm döngüler geçerli:

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 

İstediğin verir: performans çok önemli değil

>find_indices(sequence, motif) 
2 
4 
10 

Answer 2

Eğer düzenli ifade iyi bir seçim olabilir.

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

PS. eachmatch'un üçüncü argümanları "üst üste" anlamına gelir, bunu doğrulamayı unutma.

Daha iyi bir performans gerekiyorsa, belki de KMP gibi bir algoritma uygulayarak biraz zaman geçirmelisiniz.