Completing a Tree

In this problem we are asked to find out the minimum number of edges we need to add to a graph of n nodes described by a given adjacency list in order to produce a tree. I quite quickly managed to overthink the problem and got caught up trying to build the graphs described by the adjacency list, until I finally realised there is a much simpler solution.

Sample dataset:

10

1 2

2 8

4 10

5 9

6 10

7 9

Expected output:

3

The key to this problem is to realise that a tree with n nodes contains n-1 edges. If we then look at the adjacency list, every element of this list represents a node. Thus, to obtain the number of nodes needed to produce a tree, we simply need to make the calculation n-1-elements in the list. The following Python code does just that:

data = []                                          

with open('sampledata.txt', 'r') as f:             

    for line in f:                                 

        split_data = [int(x) for x in line.split()]

        data.append(split_data)                    

n = data[0][0]                                     

edges = data[1:]                                   

print(n - len(edges) - 1)                          

Overlap Graphs

In this Rosalind problem we are entering (or at least peeking in on) the world of graph theory. Graph theory has a huge number of applications in a wide variety of fields. In biology it can be used for tracking diseases, to look for breeding patterns or, as in this case, finding an overlap graph for a set of sequences.

For a given collection of sequences in FASTA-format, we are given the task to print the adjacency list of the overlap graph of the sequences with the overlap length of 3 bp. To do this, we need to compare the suffixes of all the sequences to the prefixes. When a match is found the ID of the two sequences should be printed (the ID of the sequence containing the suffix should be printed on the left and the other one should be printed on the right). To avoid directed loops in the overlap graph, we should not print any sequences that have a suffix that matches its own prefix.

Below follows my somewhat messy but working code:

from Bio import SeqIO                                                  

prefixes = []                                                          

suffixes = []                                                          

handle = open('samplefile.fasta', 'r')                                 

for record in SeqIO.parse(handle, 'fasta'):                            

    count1 = 0                                                         

    count2 = 0                                                         

    prefix = [record.id]                                               

    suffix = [record.id]                                               

    pre = ''                                                           

    suf = ''                                                           

    for nt in record.seq:                                              

        if count1 < 3:                                                 

            pre += nt                                                  

            count1 += 1                                                

    prefix.append(pre)                                                 

    for tn in reversed(record.seq):                                    

        if count2 < 3:                                                 

            suf += tn                                                  

            count2 += 1                                                

    suffix.append(''.join(reversed(suf)))                              

    prefixes.append(prefix)                                            

    suffixes.append(suffix)                                            

handle.close()                                                         

                                                                       

for i, k in enumerate(suffixes):                                       

    currentsf = suffixes[i][1]                                         

    currentid = suffixes[i][0]                                         

    for j, l in enumerate(prefixes):                                   

        if currentsf == prefixes[j][1] and currentid != prefixes[j][0]:

            print(currentid, prefixes[j][0])                           

In the first part of this program I load the prefixes and suffixes into two separate lists together with their corresponding ID. At first I tried using dictionaries for this because I thought it would be easy to extract the corresponding ID's when a match was found. Unfortunately this wasn't as straightforward as I initially thought because many of the values (the suffixes and prefixes, respectively) were identical. I wanted to use the value in one dictionary to find the corresponding key to that value in the other dictionary. I spent quite a bit of time trying to get this to work, trying several different approaches, but finally I had to give up and decided to use lists instead. However, the attempt to use dictionaries was not completely in vain, because now I know a lot more about dictionaries!