<jupyter_start><jupyter_text>Data structures Contents  Basic collection types ListsWhat do we already know about data structures?lists store collections of elements<jupyter_code>l = [1,2,3]
print(l[1]) 
for e in l:
    print(e+1)<jupyter_output>2
2
3
4<jupyter_text>Dictsdicts store pairs of values as items for rapid lookup (has embedded hash table):<jupyter_code>enzymes = { 
'EcoRI' : 'GAATTC',
'AvaII' : 'GGACC',
'BisI' : 'GCNGC' 
}

enzymes['AvaII']<jupyter_output><empty_output><jupyter_text>TuplesTuples appear to be similar to lists:<jupyter_code>t = (4, 5, 6)
print(t[1])
for e in t:
    print(e+1)<jupyter_output>5
5
6
7<jupyter_text>until we try to change one of the values:<jupyter_code>t[1] = 9<jupyter_output><empty_output><jupyter_text>Tuples are immutable; they cannot be changed once createdThis lets Python make some time/memory optimizations.Tuples are useful for storing heterogenous data (think records / rows from a table / simple objects):<jupyter_code>t1 = ('actgctagt', 'ABC123', 1)
t2 = ('ttaggttta', 'XYZ456', 1)
t3 = ('cgcgatcgt', 'HIJ789', 5)<jupyter_output><empty_output><jupyter_text>Sets{1,2,3,4,6}Sets are like lists but with- no order, and- fast lookupSet is an unordered collection of unique items. Set is defined by values separated by comma inside braces { }. Items in a set are not ordered.Hence the slicing operator [ ] does not work.<jupyter_code>a = {'apple', 'pear', 'banana'}
b = {'apple', 'pear', 'banana', 'apple'}
a==b<jupyter_output><empty_output><jupyter_text>Think of sets as either like- unordered lists with rapid lookup, or- dicts without values  A closer look at listsHopefully we are all familiar with the idea of lists of numbers and strings:<jupyter_code>[1,2,3,4]
['a', 'b', 'c']<jupyter_output><empty_output><jupyter_text>A slightly more exotic idea: we can have lists of `File` objects:<jupyter_code>files = [open("blast_result.txt"), open("sequences.fasta")]
files

['5' * 5]<jupyter_output><empty_output><jupyter_text>If we create a list where each element is also a list, we have a two-dimensional list or list-of-lists:<jupyter_code>list_of_lists = [[1,2,3],[4,5,6],[7,8,9]]
list_of_lists<jupyter_output><empty_output><jupyter_text>More readably:<jupyter_code>list_of_lists = [[1,2,3],
                 [4,5,6],
                 [7,8,9]]<jupyter_output><empty_output><jupyter_text>Each element is just a normal list:<jupyter_code>list_of_lists[1]<jupyter_output><empty_output><jupyter_text>and we can use two brackets to address one of the inner elements:<jupyter_code>list_of_lists[1][2]<jupyter_output><empty_output><jupyter_text>Where might this be useful? Imagine storing a multiple sequence alignment:<jupyter_code>aln = [['A', 'T', '-', 'T', 'G'], 
       ['A', 'A', 'T', 'A', 'G'], 
       ['T', '-', 'T', 'T', 'G'], 
       ['A', 'A', '-', 'T', 'A']]<jupyter_output><empty_output><jupyter_text>We could get a single aligned sequence<jupyter_code>aln[2]<jupyter_output><empty_output><jupyter_text>or a single column (don't worry about list comprehension if you haven't seen them yet):<jupyter_code>#get the fourth column
[seq[3] for seq in aln]<jupyter_output><empty_output><jupyter_text>We can initialize the list of lists in two ways:<jupyter_code>a = [[0, 0], [0, 0]]
print(a)
b = [[0] * 2] * 2
print(b)

a[0][0] = 1
print(a)
b[0][0] = 1
print(b)<jupyter_output>[[1, 0], [0, 0]]
[[1, 0], [1, 0]]<jupyter_text>What happened?  Lists of dicts and tuplesWe can build lists of other things too. Imagine we have a collection of DNA sequence records. We could store this a list of dicts:<jupyter_code># a list of dicts
records = [
    {'seq' : 'actgctagt', 'accession' : 'ABC123', 'genetic_code' : 1},
    {'seq' : 'ttaggttta', 'accession' : 'XYZ456', 'genetic_code' : 1},
    {'seq' : 'cgcgatcgt', 'accession' : 'HIJ789', 'genetic_code' : 5}
]

for record in records:
    print('accession number : ' + record['accession'])
    print('genetic code: ' + str(record['genetic_code']))<jupyter_output>accession number : ABC123
genetic code: 1
accession number : XYZ456
genetic code: 1
accession number : HIJ789
genetic code: 5<jupyter_text>A taxonomy of data structuresWe have looked at- lists of lists- lists of dictsIt's also possible to build lists of sets. How about other data structures? SetsElements in sets have to be immutable (so they can be hashed) so we can't build- sets of lists- sets of dicts- sets of setswe can build sets of tuples (though I'm not sure why). TuplesWe can build tuples where the individual elements are lists/sets/dicts/tuples, but they tend not to be very useful. Fun with DictsDicts of things turn out to be **very** useful. They allow us to - attach names to other data structures, and- rapidly look up other data structures using those names. Dicts of sets Imagine we have run a gene expression experiment in which we subject some cells to various metal elements and record which genes are overexpressed in response. The data might look like this:<jupyter_code>gene_sets = {
    'arsenic' : {1,2,3,4,5,6,8,12},
    'cadmium' : {2,12,6,4},
    'copper' : {7,6,10,4,8},
    'mercury' : {3,2,4,5,1}
}
gene_sets['copper']<jupyter_output><empty_output><jupyter_text>This data structure leverages the features of dicts (rapidly look up a gene set from the metal name) and sets (rapidly check membership). E.g. is gene number 3 over-expressed in response to arsenic?<jupyter_code>3 in gene_sets['arsenic']<jupyter_output><empty_output><jupyter_text>Which conditions is gene 5 over-expressed in response to?<jupyter_code>for metal, genes in gene_sets.items(): 
    if 5 in genes: 
        print(metal)<jupyter_output>arsenic
mercury<jupyter_text>Or even more concisely (wait for comprehensions....):<jupyter_code>[metal for metal, genes in gene_sets.items() if 5 in genes]<jupyter_output><empty_output><jupyter_text>Now, a more interesting question: are there any conditions whose genes are a subset of another condition's genes?<jupyter_code>for condition1,set1 in gene_sets.items(): 
     for condition2,set2 in gene_sets.items():
            if set1.issubset(set2) and condition1 != condition2: 
                print(condition1 + ' is a subset of ' + condition2)<jupyter_output>cadmium is a subset of arsenic
mercury is a subset of arsenic<jupyter_text>Notice how we use the features of both dicts (to get hold of the condition names) and sets (using the `issubset()` method). List of tuplesRemember our list of tuples for storing DNA sequence records:<jupyter_code>records = [
    ('actgctagt', 'ABC123', 1),
    ('ttaggttta', 'XYZ456', 1),
    ('cgcgatcgt', 'HIJ789', 5)
]<jupyter_output><empty_output><jupyter_text>This is great for iterating over all records:<jupyter_code>for record in records:
    (sequence, accession, code) = record
    print("looking at record " + accession + " with genetic code " + str(code))
    # do something with the record<jupyter_output><empty_output><jupyter_text>but not great for finding a specific record:<jupyter_code>for record in records:
    if record[1] == 'XYZ456':
        print("Found it!")
        (sequence, accession, code) = record
        # do something with the record<jupyter_output><empty_output><jupyter_text>Dict of tuplesHere's the same data as a dict of tuples. We turn the accession into the key:<jupyter_code>records = {
    'ABC123' : ('actgctagt', 1),
    'XYZ456' : ('ttaggttta', 1),
    'HIJ789' : ('cgcgatcgt', 5)
}
for key, val in records.items():
    if key == 'XYZ456':
        print("Found it!")
        # do something with the val<jupyter_output><empty_output><jupyter_text>Now it's just as easy to iterate over all records:  Some special data structures from the standard library `Collections.Counter`Common scenario number one: we want to count the number of times each unique element occurs in a collection of things. E.g. counting bases in a DNA sequence:<jupyter_code>dna = 'aattggaattggaattg'
base_counts = {}
for base in dna:
    current_count = base_counts.get(base, 0)
    base_counts[base] = current_count + 1

print(base_counts)<jupyter_output>{'a': 6, 't': 6, 'g': 5}<jupyter_text>`collections.Counter` is a special dict class for doing this. Construct it by passing a list (or string, etc.) as the argument:<jupyter_code>import collections

dna = 'aattggaattggaattg'
base_counter = collections.Counter(dna)

print(base_counter)
print(base_counter.most_common())
print(base_counter.get('t'))<jupyter_output>Counter({'a': 6, 't': 6, 'g': 5})
[('a', 6), ('t', 6), ('g', 5)]
6<jupyter_text>`collections.defaultdict`Common scenario number two: we want to have a dict where there's a default value for new keys. Let's tackle the exact same problem. Previously we have implicitly used zero as the default value when retrieving a key:<jupyter_code>dna = 'aattggaattggaattg'
base_counts = {}
for base in dna:
    current_count = base_counts.get(base, 0)
    base_counts[base] = current_count + 1

print(base_counts)<jupyter_output><empty_output><jupyter_text>if we use a `defaultdict` we can supply a function that will be used to create the value for a key when we ask for it.<jupyter_code>import collections

def return_zero():
    return 0

# note no parens after function name
dd = collections.defaultdict(return_zero)
dd['banana']
# or with a lambda
dd = collections.defaultdict(lambda : 0)
dd['apple']<jupyter_output><empty_output><jupyter_text>Now we can manipulate values in the dict without worrying about whether there is already a value there:<jupyter_code>dna = 'aattggaattggaattg'
base_counts = collections.defaultdict(lambda : 0)
for base in dna:
    base_counts[base] = base_counts[base] + 1
print(base_counts)


# or more concisely
base_counts = collections.defaultdict(lambda : 0)
for base in dna:
    base_counts[base] +=  1
print(base_counts)<jupyter_output><empty_output><jupyter_text>Example Transforming data between structuresUse the heavy metal gene expression data. The similarity score between two conditions is the number of over-expressed genes in common (the intersection) divided by the total number of over-expressed genes (the union). Write a program that will start with the dict of sets and produce a pairwise similarity matrix stored as a dict of dicts.  We should be able to get the score for a given pair of conditions like this:```pythonscore = similarity_matrix['arsenic']['cadmium']``` Hints- take a look at [the documentation for sets](https://docs.python.org/2/library/stdtypes.htmlset).- this is really three problems: (1) how to calculate similarity for any two given set of genes and (2) how to generate all pairs of sets of genes and (3) how to store the resulting scores.- think about what the final data structure will look like... you can figure this out from the code fragment above. Draw the final data structure if it helps.<jupyter_code>gene_sets = { 
        'arsenic' : {1,2,3,4,5,6,8,12}, 
        'cadmium' : {2,12,6,4}, 
        'copper' : {7,6,10,4,8}, 
        'mercury' : {3,2,4,5,1} 
} 
 
set1 = gene_sets['arsenic'] 
set2 = gene_sets['mercury'] 
print(set1.intersection(set2))
print(set1.union(set2))
len(set1.intersection(set2)) / len(set1.union(set2))<jupyter_output><empty_output><jupyter_text>Next, how to calculate score for each pair of conditions? We can iterate over once with `items()`:<jupyter_code>for condition, geneset in gene_sets.items():
    print(condition, geneset)<jupyter_output><empty_output><jupyter_text>So to get pairs we just need two nested loops. Let's throw in an extra `if` to avoid comparing condition to itself:<jupyter_code>for condition1, set1 in gene_sets.items(): 
    for condition2, set2 in gene_sets.items(): 
        if condition1 != condition2: 
            similarity = len(set1.intersection(set2)) / len(set1.union(set2))
            print(condition1, condition2, similarity)<jupyter_output><empty_output><jupyter_text>We still get comparisons each way i.e. mercury vs. copper and copper vs. mercury but ignore that for now.Next, how to store the results? The goal is to eventually be able to type```pythonsimilarity_matrix['arsenic']['cadmium']```so it's tempting to just create a `similarity_matrix` dict and then do this:<jupyter_code>from collections import defaultdict
similarity_scores = defaultdict(dict) 
for condition1, set1 in gene_sets.items():
    for condition2, set2 in gene_sets.items():
        if condition1 != condition2:
            similarity = len(set1.intersection(set2)) / len(set1.union(set2))
            similarity_scores[condition1][condition2] = similarity
similarity_scores
similarity_scores['arsenic']['cadmium']
# ignore this cell, it's for loading custom js code
from IPython.core.display import Javascript
Javascript(filename="custom.js")
# ignore this cell, it's for loading custom css code
from IPython.core.display import HTML
HTML(filename="custom.css")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11309989057370642, 'fraction_numerical': 0.02094731905580741, 'mean_word_length': 5.217201166180758, 'pattern_counts': {'":': 0, '<': 133, '<?xml version=': 0, '>': 133, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '35', 'dir': 'jupyter-structured-clean-dedup', 'id': '144031', 'license': 'MIT', 'n_tokens_mistral': 4460, 'n_tokens_neox': 4223, 'n_words': 1390, 'path': 'notebooks/02_3_Data_structures.ipynb', 'repo_name': 'tanicFilip/gi-2021-etf', 'size': '12794'}