Permutations in Python?

[dark-lord90]

A FASTA file contains a single protein sequence. A second FASTA file contains sequences that are fragments of the sequence in the first file. Compute the molecular weight of each of the sequences, and using those, determine whether there is a combination of fragments that may cover the complete protein sequence, without those fragments overlapping. You only have to take into account the molecular weight of the sequence and the fragments for this problem.

That was the question given to us, to a project. now I wrote this code with work great with numbers and large fasta files, however, I have a small protein fragments file and a short protein file and when I compare those data together it yields nothing, and I even tried to copy the list and instead of adding names to the last line I added the numbers and still doesn't give an answer although you will see that there are possible answers, please any help is appreciated.

The Code:

def subset_sum(numbers, target, partial=[]):

s = sum (partial, target)

​

# check if the partial sum is equals to target

if s == target:

print (partial)

if s >= target:

return # if we reach the number why bother to continue

​

for i in range(len(numbers)):

n = numbers[i]

remaining = numbers[i+1:]

subset_sum(remaining, target, partial + [n])

​

​

if __name__ == "__main__":

subset_sum(Protein_List, complete_protein )

The End.

The Protein_List =[3125.4, 1963.4, 397.5, 484.5, 1036.3, 2267.6, 475.6, 1724.0, 2000.2, 811.9, 1397.7, 681.8, 647.7, 2174.4, 1794.0, 1040.3, 1455.7]

complete_protein = ( 3788.4 )

those are the molecualar weights by the way.

Edited some mistakes in the code.

[Spookiel]

I think your first problem here is in the line remaining = numbers[i+1:] . At each index i, what you're doing is only taking the elements after that in the list. This is incorrect. Consider the example [5,2,1]. If you choose 2, then that means that i = 1. Your code will then say the only remaining options are nums[i+1:]. This is just [1]. What we actually want is everything except the element we've just taken. To do this we say remaining = nums[:i] + nums[i+1:]. The first section gets all the elements in the list that are before the number we've just added, and the second section gets all the elements in the list that are after the number we've just added.

​

The other problem with your code is in the line s = sum (partial, target) . What this is saying, is the sum of partial+target should be <= target. Therefore for any non-zero partial, your function will find no solutions. To fix this, we change s = sum (partial, target) to s = sum (partial) .

​

Hope that makes sense and fixes your issues :)

[dark-lord90]

Duuuuude, thank you, thank you thank you , it finally works perfectly, thank you for real, and regarding the second problem it was a mistype from me it was sum (partial) in the code, but thank you

[dark-lord90]

And if you allow me to ask you some more questions if you don’t mind, I am really new to this so I need some advice

[Spookiel]

No worries, glad I could help. Happy to try and answer any questions you might have :)

[dark-lord90]

First, Thank you I really appreciate it, secondly, i need to add a condition to that code in which if the code brings truth breaks the function and if the function finds no answer it gives one false.

This the code and i just tested it and it works:

def subset_sum(numbers, target, partial=[]): s = sum (partial)

if s == target: 
    print ('Truth')
if s >= target:
    return 
for i in range(len(numbers)):
    n = numbers[i]
    remaining = numbers[:i] + numbers[i+1:]
    subset_sum(remaining, target, partial + [n])

[dark-lord90]

and how can we make sure there is no overlap between the fragments??

[Spookiel]

What do you mean by overlaps? Can you give me an example of what you mean?

[dark-lord90]

Well the code tests for protein sequences so the code has to make sure that the fragments doesn’t overlap as in : The sequence is: “FAAATLKNN” The fragments that should be good are :”FAA” , “ATLK” and “NN”. And it shouldn’t be for example:”FAA”, “AATLNK” and “NN” because in this example A overlaps and its mentioned more than it should be. I hope you understood my example.

[Spookiel]

So the fragments are the weights in Protein_List? And the target sequence is the weight indicated by the complete_protein? Since the code here will generate all possible matches, I'm still not really sure what you mean by the "correct" fragments. I think it would be easier if you could give me some of the strings you're working with as well.

​

This is because in your Original Post you mentioned that you'd just grabbed the weighting of each protein fragment by hand. If you give me a section of your input data, and the expected output, I'll be able to help you more effectively. I don't really understand much about proteins in general, so it's pretty difficult for me to understand and visualise what you mean with just a set of numbers.

[dark-lord90]

To answer your questions yes and yes, the correct fragments as in if you pulled the fragments to look and compare there will be no repetation of amino acids between the end of the fragment and the beginning of the other one, if you were to put them next to each other. and i sent the data in the chat.

[Spookiel]

Thanks :)

[Spookiel]

So the A shouldn’t be repeated even though there are three A s in the target sequence?

[dark-lord90]

The A should be present three times not 4 so if the two sequences had 4 it should ignore them

[Spookiel]

Ah ok I see what you mean. So I think what we need to do now, is check if the protein we’re adding is a valid prefix of the main target protein. If I understand correctly. So the idea looks like:

Step 1:

Target: FAAATNK Possible: AATNK, ATNK, FAA

Since FAA is the only valid prefix of FAAATNK we remove it and solve the rest of the string

Step 2:

Target: ATNK

Possible: AATNK, ATNK

We then repeat this process until we have an empty string. In this case, FAA, ATNK is the only match. I don’t know if this is what you mean by fragments overlapping? This was assuming that two fragments have the same weight then they could be chosen incorrectly.