Monday, 27 January 2014

Depth-first search and breadth-first search in Python

I recently had a tree structure like this (actually from the Gene Ontology hierarchy), and wanted to traverse the tree:
If you start at node N1, there are two ways to traverse the tree:

(i) a depth-first search: this uses a 'stack', and focuses on the last item that you put onto the stack. Starting at node N1, we first put N1 on the stack. The stack is the list [N1] now.
Then we take the last item off the stack: N1 in this case. We take the parent nodes of this item (N2, N3, N4) and add them to the stack. The stack contains list [N2, N3, N4] now.
Then we take the last item off the stack: N4. We take the parent nodes of this item (N3). It is already in the stack. The stack contains list [N2, N3] now.
We take the last item off the stack: N3. We take the parent nodes of this item (N6, N7), and add them to the stack. The stack contains list [N2, N6, N7] now.
We take the last item off the stack: N7. This item has no parents. The stack is [N2, N6] now.
We take the last item off the stack: N6. We add its parents (N13) to the stack, so the stack is [N2, N13].
We take the last item off the stack: N13. It has no parents. The stack is [N2] now.
We take the last item off the stack: N2. It has no parents. The stack is empty now, so we've finished.
That is, a depth-first traversal starting at node N1 takes this route:
(ii) a breadth-first search: this uses a 'queue', and focuses on the first item that you put on the queue.
Starting at node N1, we first put N1 on the queue. The queue is list [N1] now.
Then we take the first item off the queue: N1 in this case. We take the parent nodes of this item (N2, N3, N4) and add them to the queue. The queue is list [N2, N3, N4]  now.
We then take the first item off the queue: N2 in this case. N2 has no parents. The queue is [N3, N4] now.
We take the first item off the queue: N3 in this case. Its parents (N6, N7) are added to the queue, so the queue is [N4, N6, N7] now.
We take the first item off the queue: N4. We have already seen this parent (it was in the queue previously), so we ignore it. The queue is [N6, N7] now.
We take the first item off the queue: N6. We add its parents (N13) to the queue, so the queue is [N7, N13] now.
We take the first item off the queue: N7. It has no parents. The queue is [N13] now.
We take the first item off the queue: N13. It has no parents. The queue is empty now.

That is, a breadth-first search starting at node N1 takes this route:


Python code for depth-first and breadth-first searches:
My python script tree_traversal.py has code for depth-first and breadth-first traversal of this tree (thanks to my husband Noel for help with this!) If you run it, you should get output showing the stack at each point in the depth-first search, and the queue at each point in the breadth-first search:

% python3 tree_traversal.py
Depth-first search:
('stack=', [('N1', 0)])
('stack=', [('N2', 1), ('N3', 1), ('N4', 1)])
('stack=', [('N2', 1), ('N3', 1)])
('stack=', [('N2', 1), ('N6', 2), ('N7', 2)])
('stack=', [('N2', 1), ('N6', 2)])
('stack=', [('N2', 1), ('N13', 3)])
('stack=', [('N2', 1)])
{'N13': 3, 'N1': 0, 'N2': 1, 'N3': 1, 'N4': 1, 'N6': 2, 'N7': 2}


Breadth-first search:
('queue=', [('N1', 0)])
('queue=', [('N2', 1), ('N3', 1), ('N4', 1)])
('queue=', [('N3', 1), ('N4', 1)])
('queue=', [('N4', 1), ('N6', 2), ('N7', 2)])
('queue=', [('N6', 2), ('N7', 2)])
('queue=', [('N7', 2), ('N13', 3)])
('queue=', [('N13', 3)])
{'N13': 3, 'N1': 0, 'N2': 1, 'N3': 1, 'N4': 1, 'N6': 2, 'N7': 2}


Notes on the script: pop() takes the item from the end of a list, removes it and gives it to you.

Friday, 24 January 2014

Useful vi / vim short-cuts

Some useful vi / vim short-cuts that I'm always forgetting:

Copy and paste a block of text
5Y             Copy five lines of text
P                Paste the copied text
See also here for how to copy and paste a block of text.

Show hidden characters in a file
:set list       Show hidden characters
:set unlist   Hide the hidden characters

Moving around in the file
0                 Go to the start of a line
$                 Go to the end of a line
1G              Go to the start of the file
G                Go to the end of the file

Insert 50 '-'s in a row
'.' repeats the last text-changing command. You can type a number before a command in vi for it to be done a certain number of times. For example, if you want to make a line of 50 '-'s in a row, you can type '-', then press ESC, and type '50.' to get 50 '-'s.

 Toggle auto-indenting for paste

If you want to paste in code from a python script, but don't want the intenting to be messed up, you can type:

:set paste

You can then turn this off later using:

:set nopaste  



There is a nice VI cheat sheet here.

Wednesday, 22 January 2014

The Python 'zip' function

The Python 'zip' function returns a list of tuples, where the i-th tuple contains the i-th element from the each of the argument sequences. I learnt about 'zip' in the Python course in Cambridge, and my colleague Bhavana Harsha recently reminded me about it.

Here are some examples of using 'zip':

letters = ['A', 'B', 'C', 'D', 'E']
numbers = [1, 2, 3, 4, 5]
for x, y in zip(letters, numbers):
    print(x, y)
A 1
B 2
C 3
D 4
E 5


mystring = 'gene1 species1 gene2 species2 gene3 species3 gene4 species4'
temp = mystring.split()
pairs = zip(temp[0::2], temp[1::2])
for x, y in pairs:
    print(x, y)
gene1 species1
gene2 species2
gene3 species3
gene4 species4

Note: here temp[0::2] gives the 1st, 3rd, 5th... element in the list 'temp', and temp[1::2] gives the 2nd, 4th, 6th... element in the list 'temp'.

seq1 = 'ACGTAT'
seq2 = 'ACTTTT'
bases = zip(seq1,seq2)
for x, y in bases:
    print(x, y)
A A
C C
G T
T T
A T
T T


Note that once you have expanded a 'zip' once (eg. printing it out), then it no longer holds the data. For example, if you try and print out the zip 'bases' in the last example a second time, then you won't get any result.

Thanks to Bhavana Harsha for the last example.

Calculating a similarity measure for two text strings in Python

Calculating a similarity measure for two text strings

I recently wanted to calculate a similarity measure for two text strings (actually two different short functional descriptions for the same C. elegans gene). That is, a simple measure of textual (rather than semantic) similarity.

I found a mention on stackoverflow of the 'difflib' module in the Python standard library, and found that I could do it using difflib:

import difflib

fn1 = 'protein tyrosine phosphatase activity'
fn2 = 'protein-tyrosine phosphatase'
score = difflib.SequenceMatcher(None,fn1.lower(),fn2.lower()).ratio()
print(score)

This gives a score of 0.8307692307692308 in this case.

Nice!

Finding the longest matching substring of two strings
Another thing that I wanted to do was to find the longest matching substring of two strings. Again, we can do this using difflib:

import difflib

fn1 = 'protein tyrosine phosphatase activity'
fn2 = 'protein-tyrosine phosphatase'
s = difflib.SequenceMatcher(None,fn1.lower(),fn2.lower())
s.find_longest_match(0,len(fn1),0,len(fn2))

This gives output:
 
Match(a=8, b=8, size=20)

This tells us that the longest match starts at position 8 in fn1 (ie. at the 't' of 'tyrosine') and at position 8 in fn2 (the 't' of 'tyrosine') and continues for 20 letters (until the end of 'phosphatase').

Thursday, 16 January 2014

Using CEGMA to assess gene sets

The CEGMA software can be used to assess assemblies. It can also be used to assess the gene set that you have made for an assembly. What you can do is to take your set of predicted proteins (ie. a protein fasta file), and run hmmer (hmmpfam from HMMER2) against the CEGMA file of HMMs for KOGs:
eg.
% bsub -q yesterday -J CEG.TMUE1 -G team133 -R "select[mem > 500] rusage[mem=500]" -M500 -o TMUE1.cegma.output -e TMUE1.cegma.err hmmpfam2 KOG.hmm TMUE1.pep
where KOG.hmm is the file of HMMs for KOGs, and TMUE1.pep is your fasta file of proteins, TMUE1.cegma.output will be the hmmpfam output file.

Then you can parse the hmmpfam output file to see what percent of the CEGMA HMMs had significant hits:
% parse_hmmpfam_output.pl TMUE1.cegma.output TMUE1.pep 1e-05 458
where 1e-05 is the e-value cutoff to use for the hmmpfam hits, 458 is the number of KOGs in the KOG.hmm file, and the script parse_hmmpfam_output.pl can be found here.

This gives you an idea of how complete your gene set is. If your gene set is really complete, you'd expect that there will be hits to nearly 100% of the CEGMA HMMs.

Comment 28-April-2016: If CEGMA was used as input in your gene-finding pipeline (eg. to train/guide your gene-finder), it's probably not fair to also use it to assess the completeness of your gene set, as it probably did well at finding the CEGMA genes.

Tuesday, 17 December 2013

Ensembl API workshop

I attended a great Ensembl API workshop last week in the University of Cambridge, and learnt loads of things about the Ensembl API.

The course was divided up into different sections, on the different parts of the Ensembl API (core api, variation, comparative genomics, functional genomics, etc.). The instructors set us lots of nice exercises, and I've included my answers to the exercises below.

Ensembl Compara (Comparative Genomics)
This part of the course was taught by Matthieu Muffato and Stephen Fitzgerald, whose course notes are here:
Matthieu Muffato: course notes
Stephen Fitzgerald: course notes

Exercises:
1) Print the sequence of the [Compara] Member corresponding to SwissProt protein O93279: exercise1a_compara.pl
2) Find and print the sequence of all the peptide Members corresponding to the human protein-coding gene(s) FRAS1: exercise2a_compara.pl
3) Get the multiple alignment corresponding to the family (a 'family' can contain both UniProt and Ensembl members) with the stable id ENSFM00250000006121: exercise3_compara.pl
4) Get the families that the human gene ENSG00000139618 belongs to, and print out their members (note: a 'family' can contain both UniProt and Ensembl members): exercise4_compara.pl
5) Print the protein tree with the stable id ENSGT00390000003602 (note: a 'tree' can only contain Ensembl members, not UniProt members): exercise5_compara.pl
6) Print all the members of the tree containing the human ncRNA gene ENSG00000238344: exercise6_compara.pl
7) Get all the homologues for the human gene ENSG00000229314: exercise7_compara.pl
8) Count the number of one-to-one orthologues between human and mouse: exercise8_compara.pl

Making a plot of a tree:
The script in exercise 5 above extracts the tree in several formats, the last of which is called 'display_label_composite' NHX format by Compara:
((((((BRCA2_ENSXMAG00000006974_Xmac:0.4552[&&NHX:D=N:T=8083],BRCA2_ENSORLG00000003832_Olat:0.6586[&&NHX:D=N:T=8090])Atherinomorpha:0.0644[&&NHX:D=N:B=68:T=32456],BRCA2_ENSGACG00000011490_Gacu:0.1748[&&NHX:D=N:T=69293])Smegmamorpha:0.0090[&&NHX:D=N:B=1:T=129949],((BRCA2_ENSTRUG00000006177_Trub:0.0650[&&NHX:D=N:T=31033],BRCA2_ENSTNIG00000016261_Tnig:0.1058[&&NHX:D=N:T=99883])Tetraodontidae:0.1811[&&NHX:D=N:B=93:T=31031],BRCA2_ENSONIG00000005522_Onil:0.2923[&&NHX:D=N:T=8128])Percomorpha:0.0254[&&
...
NHX:D=N:B=100:T=9005],BRCA2_ENSTGUG00000011763_Tgut:0.1201[&&NHX:D=N:T=59729])Neognathae:0.2718[&&NHX:D=N:B=100:T=8825],BRCA2_ENSACAG00000004541_Acar:0.3673[&&NHX:D=N:T=28377])Sauria:0.0344[&&NHX:D=N:B=98:T=32561],BRCA2_ENSPSIG00000011574_Psin:0.2148[&&NHX:D=N:T=13735])Sauropsida:0.1177[&&NHX:D=N:B=98:T=8457])Amniota:0.1225[&&NHX:D=N:B=100:T=32524],brca2_ENSXETG00000017011_Xtro:0.7609[&&NHX:D=N:T=8364])Tetrapoda:0.1639[&&NHX:D=N:B=6:T=32523],BRCA2_ENSLACG00000007788_Lcha:0.2902[&&NHX:D=N:T=7897])Sarcopterygii:0.2981[&&NHX:D=N:B=5:T=8287])Euteleostomi:0[&&NHX:D=N:B=0:T=117571];
If you put this into a file (eg. tree.nj), then you can make a picture of the tree using Li Heng's NJTREE software, which you can download from sourceforge, by typing, for example:
% ~alc/Documents/bin/treebest/treebest export -f 8 tree.nj > tree.eps
Here -f8 sets the font size to be 8 in the image. Here's the picture:

























It doesn't show the duplication and speciation nodes in different colours, but that's ok.
[Note to self: it's possible to make a PNG that has the duplication and speciation nodes in different colours by using Li Heng's Perl script. You need to copy the tree.nj file to /nfs/users/nfs_a/alc/Documents/bin/njtree_plot, then type:
% perl nhxplot.pl tree.nj > tree.png
This gives:



































You can see the duplication nodes in red and speciation nodes in blue. Very nice! ]

Ensembl Compara Perl API documentation
The documentation for the Ensembl Compara Perl API is at http://www.ensembl.org/info/docs/api/index.html
To see the documentation for an old version of the API, eg. for Ensembl 75, replace the 'www' in the address by 'e75' for example: http://e75.ensembl.org/info/docs/api/index.html

Tuesday, 10 December 2013

Creating a password-protected zip file using 7-zip

If you want to share data with collaborators, you might want to put a password-protected zip file on the web for them to download.

If you have data in a Linux directory mydir, you can create a tar file of that directory using:
% tar cvf mydir.tar mydir

If you have 7-zip installed, you can then create a password-protected zip version of mydir.tar by typing:
% 7za a -tzip -pMYPASSWORD -mem=AES256 mydir_secure.zip mydir.tar
where the password is set to 'MYPASSWORD'

If you collaborator has 7-zip installed on a Linux machine, the zip file can be unzipped using:
% 7za e secure.zip
This will ask for the password to be entered.

I haven't tested it, but I'm guessing that your collaborator could also unzip the file using 7-zip on a Windows machine.

Thanks to this handy webpage for information: http://xmodulo.com/2013/09/how-to-create-encrypted-zip-file-on-linux.html