Difference between revisions of "BIO Assignment 4 2011"

From "A B C"
Jump to navigation Jump to search
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
<!-- {{Template:Active}} -->
+
<!-- {{Template:Inactive}} -->
{{Template:Inactive}}
+
{{Template:Active}}
  
  
Line 9: Line 9:
  
 
<div style="padding: 5px; background: #A6AFD0;  border:solid 1px #AAAAAA; font-size:200%;font-weight:bold;">
 
<div style="padding: 5px; background: #A6AFD0;  border:solid 1px #AAAAAA; font-size:200%;font-weight:bold;">
Assignment 4 - Phylogenetic Analysis
+
Assignment 4 (last: 2011) - Phylogenetic Analysis
 
</div>
 
</div>
  
Line 22: Line 22:
 
... but does evolution make sense in the light of biology?
 
... but does evolution make sense in the light of biology?
  
As we have seen in the previous assignments, the Mbp1 transcription factor has homologues in all other fungi, yet - looking at orthologues - this is not always a clear one-to-one mapping of related genes to each other. It appears that various systems of APSES domain transcription factors have evolved independently. Of course this bears directly on our notion of ''function'' - what it means to say that two genes in different organisms have the "same" function. In case two organisms both have an orthologous gene for the same, distinct function, this may be warranted. But what if that gene has duplicated in one of them, and the two paralogues now perform different, related functions in one organism? In order to be able to even ask such questions, we need to understand how we can make the evolutionary history of gene families explicit. This is the domain of '''phylogenetic analysis'''. We can ask questions like: how many paralogues did the cenancestor of a clade possess? Which of these underwent additional duplications in the phylogenesis of the organism I am studying? Did any genes get lost? And - adding additional biological insight to the picture - did the observed duplications lead to the "invention" of new biological systems? When was that? And how did the species benefit from this event?
+
As we have seen in the previous assignments, the Mbp1 transcription factor has homologues in all other fungi, yet there is not always a clear one-to-one mapping between members of a family in distantly related species. It appears that various systems of APSES domain transcription factors have evolved independently. Of course this bears directly on our notion of function - what it means to say that two genes in different organisms have the "same" function. In case two organisms both have an orthologous gene for the same, distinct function, saying that the function is the same may be warranted. But what if that gene has duplicated in one species, and the two paralogues now perform different, related functions in one organism? Theses two are still orthologues to the other species, but now we expect functionally significant residues to have adapted to the new role of one paralogue. In order to be able to even ask such questions, we need to make the evolutionary history of gene families explicit. This is the domain of '''phylogenetic analysis'''. We can ask questions like: how many paralogues did the cenancestor of a clade possess? Which of these underwent additional duplications in the phylogenesis of the organism I am studying? Did any genes get lost? And - adding additional biological insight to the picture - did the observed duplications lead to the "invention" of new biological systems? When was that? And perhaps even: how did the species benefit from this event?
  
We will develop this kind of analysis in this assignment. In the previous assignment you have established which genes are the reciprocally most closely related orthologues to Mbp1 and to other yeast APSES domain genes. In this assignment, we will analyse their evolutionary relationship and compare it to the evolutionary relationship of all fungal APSES domains. The goal is to define families of related transcription factors and their evolutionary history.
 
  
A number of good tools for phylogenetic analysis exist; ''general purpose packages'' include the (free) [http://evolution.genetics.washington.edu/phylip.html PHYLIP] package and the (commercial) PAUP package. ''Specialized tools'' for tree-building include Treepuzzle or Mr. Bayes. This assignment is conctructed around programs that are availble in PHYLIP, however you are welcome to use other tools that fulfil a similar purpose if you wish. In this field, researchers consider trees that have been built with ML (maximum likelihood) methods to be more reliable than trees that are built with parsimony methods, or distance methods such as NJ (Neighbor Joining). However ML methods are also much more compute-intensive. Just like with multiple sequence alignments, some algorithms will come closer to guessing the truth and others will not and usually it is hard to tell which is the more trustworthy of two diverging results. The prudent researcher tries out alternatives and forms her own opinion. Specifically, we may usually assume results that converge, independent of the algorithm, to be more reliable than those that depend strongly on a particular algorithm or details of input data.
+
We will develop this kind of analysis in this assignment. In the previous assignment you have established which gene in your species is the reciprocally most closely related orthologue to yeast Mbp1 and you have identified the full complement of APSES domain genes in your assigned organism. In this assignment, we will analyse these genes' evolutionary relationship and compare it to the evolutionary relationship of all fungal APSES domains. The goal is to define families of related transcription factors and their evolutionary history.
  
But regarding algorithm and rersources: we will take two shortcuts in this assignment (and both shortcuts are things you should not do ''in real life''):
+
A number of excellent tools for phylogenetic analysis exist; ''general purpose packages'' include the (free) [http://evolution.genetics.washington.edu/phylip.html PHYLIP] package and the (commercial) PAUP package. ''Specialized tools'' for tree-building include Treepuzzle or Mr. Bayes. This assignment is constructed around programs that are available in PHYLIP, however you are welcome to use other tools that fulfill a similar purpose if you wish. In this field, researchers consider trees that have been built with ML (maximum likelihood) methods to be more reliable than trees that are built with parsimony methods, or distance methods such as NJ (Neighbor Joining). However ML methods are also much more compute-intensive. Just like with multiple sequence alignments, some algorithms will come closer to guessing the truth and others will not and usually it is hard to tell which is the more trustworthy of two diverging results. The prudent researcher tries out alternatives and forms her own opinion. Specifically, we may usually assume results that converge when computed with different algorithms, to be more reliable than those that depend strongly on a particular algorithm, parameters, or details of input data.
  
'''One''': we will use an '''efficient''' tree-building algorithm, not the best-available one. This is an algorithm which is available through an online Webserver, without the need for you to install software on your own machine. In ''real life'' you would of course use the most accurate algortihm you can get, regardless of the resources this requires, since it makes no sense to waste your time on a careful analysis of inaccurate trees. Your supervisor would want it so as well. And if not she, the reviewers of your manuscript. <small>(However, the simpler algorithm we use here apears to give results that appear quite plausible for the situation we are studying.)</small>
+
However: regarding algorithm and resources, we will take a shortcut in this assignment (something you should not do in real life). We will assume that the tree the algorithm constructs is correct. In "real life" you would establish its reliability with a bootstrap procedure: repeat the tree-building a hundred times with partial data and see which branches and groupings are robust and which depend on the details of the data. In this assignment, we should simply acknowledge that bifurcations that are very close to each other have not been "resolved" and be appropriately cautious in our inferences. In phylogenetic analysis, not all lines a program draws are equally trustworthy. Don't take the trees as a given fact just because a program suggests this. Look at the evidence, include independent information where available, use your reasoning, and analyse the results critically. As you will see, there are some facts that we know for certain: we know which species the genes we have sequenced come from, and we can (usually) make good assumptions about the relationship of the species themselves - the history of speciation events that underlies all evolution of genes. This is extremely helpful information for our work.  
  
'''Two''': we will assume the tree the algorithm constructs is ''correct''. In ''real life'' you would establish its reliability with a bootstrap procedure: repeat the tree-building a hundred times with partial data and see which branches and groupings are robust and which depend on the details of the data. However, we should acknowledge that bifurcations that are very close to each other have not been" resolved". Any conscientious reviewer would flag such leniency and send your results back to you for a bootstrapping exercise at the computer. In phylogenetic analysis, not all lines a program draws are equally trustworthy. Dont take the trees as a given fact just because a program suggests this. Look at the evidence, include independent information where available, use your reasoning, and analyse the reults critically.
+
=====Introduction: Tasks=====
  
In case you want to review concept of trees, clades, LCAs OTUs and the like, I have linked an excellent and very understandable introduction-level [http://biochemistry.utoronto.ca/undergraduates/courses/BCH441H/restricted/Baldauf_2003_PhylogenyTutorial.pdf article on phylogenetic analysis (pdf)] here and to the resource section at the bottom of this page.
+
For this assignment, we start from the APSES domains you have collected previously. You will align these domains with a set of reference domains and edit the alignment to make it suitable for phylogenetic analysis, using Jalview. Then you will construct a phylogenetic tree and interpret the tree. The goal is to identify orthologues and paralogues. <!-- Optionally, you will look at structural and functional conservation of residues. -->
 +
 
 +
In case you want to review concept of trees, clades, LCAs, OTUs and the like, I have linked an excellent and very understandable introduction-level [http://biochemistry.utoronto.ca/undergraduates/courses/BCH441H/restricted/Baldauf_2003_PhylogenyTutorial.pdf article on phylogenetic analysis (pdf)] here and to the resource section at the bottom of this page.
  
 
&nbsp;
 
&nbsp;
Line 42: Line 43:
 
num=4|
 
num=4|
 
ord=fourth|
 
ord=fourth|
due = Monday, November 17 at 10:00 in the morning}}
+
due = Monday, November 28 at 12:00 in the morning}}
  
 
;Your documentation for the procedures you follow in this assignment will be worth 1 mark.
 
;Your documentation for the procedures you follow in this assignment will be worth 1 mark.
Line 50: Line 51:
  
 
<div style="padding: 5px; background: #BDC3DC;  border:solid 1px #AAAAAA;">
 
<div style="padding: 5px; background: #BDC3DC;  border:solid 1px #AAAAAA;">
 +
 
==(1) Preparations==
 
==(1) Preparations==
 
</div>
 
</div>
Line 60: Line 62:
 
&nbsp;<br>
 
&nbsp;<br>
  
=====Introduction: Task=====
 
 
For this assignment, we start from the multiple sequence alignments we have constructed previously. We will edit the alignment to make it suitable for phylogenetic analysis. We will construct a phylogenetic tree and we will analyse the tree.
 
For this assignment, we start from the multiple sequence alignments we have constructed previously. We will edit the alignment to make it suitable for phylogenetic analysis. We will construct a phylogenetic tree and we will analyse the tree.
  
The phylogenetic tree we will construct will represent all APSES domains of the species we have analyzed. In order to '''interpret''' such a tree it is crucial to have some sense of what these domains are, i.e. to cluster them according to their orthologues. Only then can we analyse the tree by asking which subclades mirror the accepted phylogeny of fungi and which ones differ. In the third assignment, we have assigned orthology from reciprocal best match analysis. Based on this information, I have revised the gene names in the [[APSES_domains_MUSCLE_revised|'''MUSCLE alignment of all APSES domains''']]. When we calculate a phylogenetic tree with these sequences, we should expect orthologues to cluster into the same subclade. Of course, not all fungi have the same number of APSES domain homologues, but from the data we have compiled it should be possible to define their evolutionary history with reference to the other species.
+
=====Introduction: Principle=====
 +
 
 +
In order to use molecular sequences for the construction of phylogenetic trees, you have to build a multiple alignment first, then edit it. This is important: all rows of sequences have to contain the exact same number of characters and to hold '''aligned characters in corresponding positions'''. Phylogeny programs are not meant to revise an alignment but to analyze evolutionary relationships, '''after''' the alignment has been determined. The program's inferences are made on a column-wise basis and if your columns contain data from unrelated positions, the inferences are going to be questionable.
  
=====Introduction: Principle=====
+
The result of the tree construction is a decision about the most likely evolutionary relationships. Fundamentally, tree-construction programs decide which sequences had common ancestors.
In order to use molecular sequences for the construction of phylogenetic trees, you have to build a multiple alignment first, then edit it. This is important: all rows of sequences have to contain the exact same number of characters and to hold '''aligned characters in corresponding positions'''. Phylogeny programs are not meant to revise an alignment but to analyse evolutionary relationships, given the alignment. Their inferences are made on a column-wise basis and if your columns contain data from unrelated positions, the inferences are going to be questionable.
 
  
The result of the tree construction is a decision about the most likely evolutionary relationships. Fundamentally, tree-construction programs decide which sequences had common ancestors.
 
  
 
'''Distance based''' phylogeny programs start by using sequence comparisons to estimate evolutionary distances:
 
'''Distance based''' phylogeny programs start by using sequence comparisons to estimate evolutionary distances:
* they apply a model of evolution such as a mutation data matrix, to calculate a score for each '''pair''' of sequences,
+
 
 +
* they apply a model of evolution such as a mutation data matrix, to calculate a score for each pair of sequences,
 
* this score is stored in a "distance matrix" ...
 
* this score is stored in a "distance matrix" ...
* ... and used to estimate a tree that goups sequences with close relationships together. (e.g. by using an NJ, Neigbor Joining, algorithm).  
+
* ... and used to estimate a tree that groups sequences with close relationships together. (e.g. by using an NJ, Neigbor Joining, algorithm).  
 +
 
 
They are fast, can work on large numbers of sequences, but are less accurate if genes evolve at different rates.
 
They are fast, can work on large numbers of sequences, but are less accurate if genes evolve at different rates.
 +
  
 
'''Parsimony based''' phylogeny programs build a tree that minimizes the number of mutation events that are required to get from a common ancestral sequence to all observed sequences. They take all columns into account, not just a single number per sequence pair, as the Distance Methods do. For closely related sequences they work very well, but they construct inaccurate trees when they can't make good estimates for the required number of sequence changes.
 
'''Parsimony based''' phylogeny programs build a tree that minimizes the number of mutation events that are required to get from a common ancestral sequence to all observed sequences. They take all columns into account, not just a single number per sequence pair, as the Distance Methods do. For closely related sequences they work very well, but they construct inaccurate trees when they can't make good estimates for the required number of sequence changes.
  
'''ML''', or '''Maximum Lieklihood''' methods attempt to find the tree for which the observed sequences would be the most likely under a particular evolutionary model. They are based on a rigorous statistical framework and yield the most robust results. But they are also VERY compute intensive and a tree of the size that we are building in this assignment is already almost beyond the resources of common workstations (runs about a day on my computer). However, one may split a large problem into smaller, obvious subtrees (e.g. analysing orthologues as a group, only including a few paralogues for comparison) and then merge the smaller trees; this way even very large problems can become tractable. They also suffer less from "long-branch attraction" - the phenomenon that weakly similar sequences can be grouped inappropriately close together in a tree due to spurious shared differences.
 
  
Clearly, in order for tree-estimation to work, one must not include fragments of sequence which have evolved under a different evolutionary model as all others, e.g. after domain fusion, or after accommodating large stretches of indels. Thus it is appropriate to edit the sequences and pare them down to a ''most characteristic subset'' of amino acids. The goal is not to be as comprehensive as possible, but to input those columns of aligned residues that will best represent the ''true'' phylogenetic relationships between the sequences.
+
'''ML''', or '''Maximum Likelihood''' methods attempt to find the tree for which the observed sequences would be the most likely under a particular evolutionary model. They are based on a rigorous statistical framework and yield the most robust results. But they are also quite compute intensive and a tree of the size that we are building in this assignment is a challenge for the resources of common workstation (runs about an hour on my computer). If the problem is too large, one may split a large problem into smaller, obvious subtrees (e.g. analysing orthologues as a group, only including a few paralogues for comparison) and then merge the smaller trees; this way even very large problems can become tractable.
  
=====Introduction: Problems=====
+
ML methods suffer less from "long-branch attraction" - the phenomenon that weakly similar sequences can be grouped inappropriately close together in a tree due to spuriously shared differences.
Gaps are a real problem here, as usual. Strictly speaking, the similarity score of an '''alignment''' program as well as the distance score of a '''phylogeny''' program are not calculated for an ordered ''sequence'', but for a ''sum of independent values'', one for each aligned columns of characters. The order of the columns does not change the score. Hoever in an optimal sequence alignment with gaps, this is no longer strictly true since a one-character gap creation has a different penalty score than a one-character gap extension! Most '''alignment''' programs use a model with a constant gap insertion penalty and a linear gap extension penalty. This is not rigourously justified from biology, but parametrized (or you could say "tweaked") to correspond to our observations. However, most '''phylogeny''' programs, (such as the programs in PHYLIP) do not work in this way. PHYLIP strictly operates on columns of characters and treats a gap character just like a residue with the one letter code "-". Thus gap insertion- and extension- characters get the samescore. For short indels, this '''underestimates''' the distance between pairs of sequences, since any evolutionary model should reflect the fact that gaps are much less likely than point mutations. If the gap is very long though, all events are counted individually as many single substitutions (rather than one lengthy one) and this '''overestimates''' the distance. And it gets worse: long stretches of gaps can make sequences appear similar in a way that is not justified, just because they are identical in the "-" character. It is therefore common and acceptable to edit gaps in the alignment to one or two character, or to remove them.
 
  
=====Introduction: Practice=====
 
In practice, follow the fundamental principle that '''all characters in a column should be related by homology'''. This implies the following rules of thumb:
 
  
:*Remove all stretches of residues in which the ''alignment'' appears ambiguous (not just highly variable, but ambiguous regarding the aligned positions).
+
Clearly, in order for tree-estimation to work, one must not include fragments of sequence which have evolved under a different evolutionary model as all others, e.g. after domain fusion, or after accommodating large stretches of indels. Thus it is appropriate to edit the sequences and pare them down to a most characteristic subset of amino acids. The goal is not to be as comprehensive as possible, but to input those columns of aligned residues that will best represent the true phylogenetic relationships between the sequences.
:*Remove all frayed N- and C- termini, especially regions in which not all sequences that are being compared appear homologous and that may stem from unrelated domains.
 
:*Remove all but approximately one column from gapped regions, and all residues N- and C- terminal of the gap in which the alignment appears questionable. ( I would keep one gapped column as a placeholder for a rare and very distinct evolutionary event, rather than simply deleting them all, some researchers remove all gaps).
 
:*Also, consider that neither residues that are completely different between all species, nor residues that are completely conserved are informative for relationship distances.
 
:*If your sequences are too long, you may run out of memory. 60-80 aligned residues should be plenty and if the sequences fit on a single line you will save yourself potential trouble with block-wise vs. interleaved input.
 
  
:<small>(A '''very''' useful trick with Microsoft Word is that you can select blocks of text and entire columns in the document with your mouse: hold the "ALT" key depressed while you click and drag your mouse to select. This will greatly facilitate the preparation of sequences. You can treat that selection as any other selected text: color or highlight characters, or delete them. Importantly, you can also cut and paste entire columns! Of course, this will only work as expected if you use a fixed-width font such as Courier or "Courier New". )</small>
+
=====Introduction: Gaps=====
  
The preparation of the input file of aligned residues, used by the PHYLIP package is straightforward in principle; just carefully follow the instructions in PHYLIP's well written documentation. If you plan to use an outgroup for your tree, it is a good idea to move that to the first line of your alignment, since this is where PHYLIP will look for it by default.
+
Gaps are a real problem here, as usual. Strictly speaking, the similarity score of an '''alignment''' program as well as the distance score of a '''phylogeny''' program are not calculated for an ordered sequence, but for a sum of independent values, one for each aligned columns of characters. The order of the columns does not change the score. However in an optimal sequence alignment with gaps, this is no longer strictly true since a one-character gap creation has a different penalty score than a one-character gap extension! Most '''alignment''' programs use a model with a constant gap insertion penalty and a linear gap extension penalty. This is not rigorously justified from biology, but parametrized (or you could say "tweaked") to correspond to our observations. However, most '''phylogeny''' programs, (such as the programs in PHYLIP) do not work in this way. PHYLIP strictly operates on columns of characters and treats a gap character just like a residue with the one letter code "-". Thus gap insertion- and extension- characters get the same score. For short indels, this '''underestimates''' the distance between pairs of sequences, since any evolutionary model should reflect the fact that gaps are much less likely than point mutations. If the gap is very long though, all events are counted individually as many single substitutions (rather than one lengthy one) and this '''overestimates''' the distance. And it gets worse: long stretches of gaps can make sequences appear similar in a way that is not justified, just because they are identical in the "-" character. It is therefore common and acceptable to edit gaps in the alignment and delete all but one or two columns of gapped sequence, or to remove such columns altogether.
  
Some notes on how to avoid common editing troubles. Copy the sequences from the pages linked from the ''Resources'' section below. Paste them into a document, using the Word "Edit &rarr; Paste special &rarr; Unformatted text". Set the page-setup to "landscape", the font-size to something small, then you can put every sequence into one line. Take special note that your files must not include tab characters! (Tabs are counted as one single character by the phylogeny programs.) You can use Word to globally replace all tabs (specified as "^t") with a blank, to make sure. Spaces count, so display your alignment in a fixed-width font, such as Courier (or "Courier New"), not a proportional-width font such as Times, Arial, or Helvetica, and ensure all columns in your alignments align as they should. As always, make sure you save your input files as "Text Only".
 
  
<small>
+
=====Introduction: The outgroup=====
:A note if you are  working on a '''Mac''' and saving input on disk, to run with a locally installe PHYLIP version: here MS Word will play one of its usual [http://en.wikipedia.org/wiki/Shenanigan shenanigans] on you since it writes text files with the old-style OS 9 Carriage Return characters <code>(\r; ASCII 13; hex 0D; CR)</code>. Just by looking at the file, this is quite invisible but such "Carriage returns" are not going to be recognized by PHYLIP and most other UNIX based programs. It may not make a difference when you paste your sequences to a Web server; but if you compute things locally it will appear to the program as though all the input would be passed in one single, very long line). And this can (and did) lead to head-banging rounds of frustration. You need to replace them with '''Linefeed''' resp. '''Newline''' characters <code>(\n; ASCII 10; hex 0A; LF)</code> and you can't even do that within Word(!). Open a UNIX terminal window and navigate to the directory where your files reside. Then type:
 
  
:'''tr "\r" "\n" &lt; infile    &gt; outfile'''
+
To analyse phylogenetic trees it is useful (and for some algorithms required) to define an outgroup, a sequence that presumably diverged from all other sequences in a clade before they split up among themselves. Wherever the outgroup inserts into the tree, this is the root of the rest of the tree. And whenever a molecular clock is assumed, the branching point that connects the outgroup can be assumed to be the oldest divergence event. I have defined an outgroup sequence and added it to the [[Reference APSES domains|reference APSES domains page]]. The procedure is explained in detail on that page.
  
:... where outfile is different from infile (careful: if a file by the name of outfile already exists, '''tr''' will cheerfully overwrite it.) Alternatively you could type the following perl one-line program :
+
>gi|301025594|ref|ZP_07189117.1| KilA-N domain protein [Escherichia coli MS 69-1]
 +
<span style="color: #999999;">MTSFQLSLISRE</span>IDGEIIHLRAKDGYINATSMCRTAGKLLSDYTRLKTTQEFFDELSRDMGIPISELIQS
 +
FKGGRPENQGTWVHPDIAINLAQ<span style="color: #999999;">WLSPKFAVQVSRWVREWMSGERTTAEMPVHLKRYMVNRSRIPHTHFS
 +
ILNELTFNLVAPLEQAGYTLPEKMVPDISQGRVFSQWLRDNRNVEPKTFPTYDHEYPDGRVYPARLYPNE
 +
YLADFKEHFNNIWLPQYAPKYFADRDKKALALIEKIMLPNLDGNEQF</span>
 +
''E. coli'' KilA-N protein. Residues that do not align with APSES domains are shown in grey.
  
:'''perl -e 'while(&lt;&gt;){tr/\r/\n/;print}'  &lt; infile    &gt; outfile'''
+
=====Preparing APSES sequences=====
</small>
 
  
 +
<div style="padding: 5px; background: #DDDDEE;">
 +
#Navigate to the [[Reference APSES domains|reference APSES domains page]] and copy the sequences.
 +
#Open Jalview, select '''File &rarr; Input Alignment &rarr; from Textbox''' and paste the sequences into the textbox.
 +
#Add the APSES domain sequences '''from your species''' that you have defined in the previous assignment.
 +
#When all the sequences are present, click on '''New Window'''.
 +
#In Jalview, select Web Service &rarr; Alignment &rarr; MAFFT Multiple Sequence Alignment. The alignment is calculated in a few minutes and displayed in a new window.
 +
#Choose any colour scheme and add '''Colour &rarr; by Conservation'''. Adjust the slider left or right to see which columns are highly conserved.
 +
#Save the alignment as a Jalview project before editing it for phylogenetic analysis. You may need it again.
 +
</div>
  
In your assignment submission, clearly highlight or otherwise color the columns that you have selected, annotate why you have selected them and paste your resulting input file as well. Here is an example of what this might look like:
 
  
 +
=====Introduction: Alignment editing for phylogenetic reconstruction=====
  
[[Image:EditingGuide.jpg|frame|none|(Possible) steps in editing a multiple sequence alignment towards a PHYLIP input file. '''a''': raw alignment (CLUSTAL format); '''b''': sequences assembled into single lines; '''c''': columns to be deleted highlighted in red - 1, 3 and 4: large gaps; 2: uncertain alignment and 5: frayed C-terminus: both would put non-homologous characters into the same column; '''d''': input data for PHYLIP: names for sequences must not be longer than 10 characters, the first line must contain the number of sequences and the sequence length. PHYLIP is very picky about incorrectly formatted input, read the [http://evolution.genetics.washington.edu/phylip/doc/sequence.html PHYLIP sequence format guide].]]
+
In practice, follow the fundamental principle that '''all characters in a column should be related by homology'''. This implies the following rules of thumb:
  
=====Introduction: Web Service and data=====
+
*Remove all stretches of residues in which the ''alignment'' appears ambiguous (not just highly variable, but ambiguous regarding the aligned positions).
 +
*Remove all frayed N- and C- termini, especially regions in which not all sequences that are being compared appear homologous and that may stem from unrelated domains.
 +
*Remove all gapped regions that appear to be alignment artefacts due to inappropriate input sequences.
 +
*Remove all but approximately one column from gapped regions '''in those cases where the presence of several related insertions suggest that the indel is real, and not just an alignment artefact.''' (Some researchers simply remove all gapped regions).
 +
*Remove sections N- and C- terminal of gaps where the alignment appears questionable. 
 +
*Also, consider that neither residues that are completely different between all species, nor residues that are completely conserved are informative for relationship distances.
 +
*If your sequences are too long, your tree calculations may run out of memory. 60-80 aligned residues should be plenty and if the sequences fit on a single line you will save yourself potential trouble with block-wise vs. interleaved input.If you do run out of memory try removing columns of sequence.
 +
*Move the KilA-N outgroup sequence to the first line of your alignment, since this is where PHYLIP will look for it by default.
  
You have two choices for completing the assignment: either to use one of the [http://evolution.gs.washington.edu/phylip/phylipweb.html PHYLIP on-line servers] that generously provide public computing resources, or to download and install the [http://evolution.genetics.washington.edu/phylip.html PHYLIP program package] on your own computer at home. If you choose the former, one of your options is the [http://bioweb.pasteur.fr/seqanal/phylogeny/phylip-uk.html '''PHYLIP''' service at the '''Institut Pasteur'''] in France.
 
  
<small>I have tried the Pasteur service many times, and it works - however not always entirely without problems. Uninformative errors may occur when your input is too large for the system's memory (like: "sequences not aligned" ... "out of memories" and such) and once, after submitting a number of jobs, the system locked me out to wait until results would be received by e-mail (which then hasn't happened). Regrettably, this is not documented. However the integration of their services in a logical sequence of steps is very convenient and some of their services use algorithms that improve on PHYLIP. If you rather decide to install PHYLIP, good for you. That is easy to do, well documented, there are much less limitations on memory - but if you don't read and understand the instructions carefully, you may be in for a spell of frustration.</small>
 
  
Either way, I have posted typical input files and result files on the [[Assignment_5_fallback_data|fallback data page]], to allow you to bail out in case technical problems become overwhelming. If you use the data posted here instead of your own, you '''must''' document that fact and explain what you have tried, and why that has failed. The posted data is a fallback, not a shortcut.
+
[[Image:EditingGuide.jpg|frame|none|(Possible) steps in editing a multiple sequence alignment towards a PHYLIP input file. '''a''': raw alignment (CLUSTAL format); '''b''': sequences assembled into single lines; '''c''': columns to be deleted highlighted in red - 1, 3 and 4: large gaps; 2: uncertain alignment and 5: frayed C-terminus: both would put non-homologous characters into the same column; '''d''': input data for PHYLIP: names for sequences must not be longer than 10 characters, the first line must contain the number of sequences and the sequence length. PHYLIP is very picky about incorrectly formatted input, read the [http://evolution.genetics.washington.edu/phylip/doc/sequence.html PHYLIP sequence format guide].]]
  
For this assignment, we will use a simple distance based tree construction method, specifically the UPGMA variant of the neighbor joining algorithm. This represents a reasonable compromise between accuracy and speed, especially when applied to moderately dissimilar sequences. In general, distance methods include '''two''' steps: (1) calculate a pairwise-distance matrix between sequences, (2) construct a tree, based on the matrix. Thus all the information in the alignment bewtween two pairs of sequences is collapsed into a single number: their pairwise distance. Alternative approaches, parsimony as well as ML based algorithms, take individual columns into account.
+
;Once you are satisfied with your editing, proceed as follows:
  
&nbsp;<br>
 
 
<div style="padding: 5px; background: #DDDDEE;">
 
<div style="padding: 5px; background: #DDDDEE;">
Prepare an input file that is representative of the APSES domains.
+
#Download the PHYLIP package from the [http://evolution.genetics.washington.edu/phylip.html Phylip homepage] and install it on your computer.
 
+
#Prepare a PHYLIP input file from your Jalview alignment. The simplest way to achieve this appears to be:
*Access the [[APSES_domains_MUSCLE_revised|revised MSA for all APSES domains]], linked here (and from the resources section at the bottom of the page). Prepare a PHYLIP formatted input file from this MSA, restricting the number of sequence characters to no more than 70. Read the [http://evolution.genetics.washington.edu/phylip/doc/main.html#inputfiles PHYLIP format documentation] and follow the considerations dicussed above. ([[Assignment_5_fallback_data|See the fallback data in case you get stuck]], but you '''must''' prepare (and document) an input file according to the instructions, even if you end up using the fallback data for whatever reason.) Do not forget to document how you have prepared your input file: define where your source-sequences came from, define which columns you have deleted by highlighting the deleted residues in one sequence, and include your input file in the assignment.
+
##In Jalview, use '''File &rarr; Output to Textbox&rarr;FASTA''', then '''Edit&rarr;Select All''' and '''Edit&rarr;copy''' the sequences.
 +
##In a browser, navigate to the [http://www-bimas.cit.nih.gov/molbio/readseq/ '''Readseq sequence conversion service'''].
 +
##Paste your sequences into the form and choose '''Phylip''' as the output format. Click on '''submit'''.
 +
##Save the resulting page as a text file in the directory where the phylip executables reside on your computer. Give it some useful name such as <code>All-APSES_domains.phy</code>.
 +
#Make a copy of that file and name it <code>infile</code>. Note: make sure that your Microsoft Windows operating system does not silently append the extension ".txt" to your file. It should be called "infile", nothing else and you should never, never, ever permit your operating systems to slyly hide file extensions from you when it displays filenames. You have been warned.  
 
</div>
 
</div>
  
&nbsp;<br>
 
&nbsp;<br>
 
  
 
<div style="padding: 5px; background: #E9EBF3;  border:solid 1px #AAAAAA;">
 
<div style="padding: 5px; background: #E9EBF3;  border:solid 1px #AAAAAA;">
Line 145: Line 158:
 
<div style="padding: 5px; background: #DDDDEE;">
 
<div style="padding: 5px; background: #DDDDEE;">
  
*Using the '''protdist''' program of PHYLIP, calculate a distance matrix for the input file you have prepared. ([[Assignment_5_fallback_data|See the fallback data in case you get stuck]]) (1 mark)
+
*Use the '''proml''' program of PHYLIP (protein sequences, maximum likelihood tree) to calculate a phylogenetic tree. Use the default parameters except that you must change option <code>S: Speedier but rougher analysis?</code> to No - your analysis should not sacrifice accuracy for speed. The calculation will take a while.
 
 
*If you use the PHYLIP Webserver, select the neighbor joining algorithm from the menu options ('''neighbor''' on the PHYLIP server) and click the button "run the selected program on outfile" ; on the next form, click the button to the "advanced neighbor form", choose the option "UPGMA" and click on the button "run neighbor". When the program is done, select the option '''drawgram''' and click '''Run the selected program on outtree'''. Choose a '''cladogram''' tree-style and a suitable output format (e.g. postscript). Paste the trees into your assignment.
 
 
 
*If you use a locally installed version of PHYLIP use '''neighbor''' with the UPGMA method to construct a tree for the input file. Open the file '''outfile''' in a text-editor, copy and paste the trees into your assignment.
 
 
 
In both cases, the process is: <code>protdist</code> &rarr; <code>neighbor</code> &rarr; <code>drawgram</code>
 
  
 
</div>
 
</div>
Line 160: Line 167:
 
<div style="padding: 5px; background: #BDC3DC;  border:solid 1px #AAAAAA;">
 
<div style="padding: 5px; background: #BDC3DC;  border:solid 1px #AAAAAA;">
  
==(2) Analysis (3 marks)==
+
==(2) Analysis (2 marks)==
 
</div>
 
</div>
  
 
I have constructed a cladogram for the species we are analysing, based on data published for 1551 fungal ribosomal sequences. Such reference tres from rRNA data are a standard method of phylogenetic analysis, supported by the assumption that rRNA sequences are monophyletic and have evolved under comparable selective pressure in all species.
 
I have constructed a cladogram for the species we are analysing, based on data published for 1551 fungal ribosomal sequences. Such reference tres from rRNA data are a standard method of phylogenetic analysis, supported by the assumption that rRNA sequences are monophyletic and have evolved under comparable selective pressure in all species.
  
[[Image:FungiCladogram.jpg|frame|none|Cladogram of fungi studied in the assignments. This cladogram is based on small subunit ribosomal rRNA sequences, and largely follows ''Tehler et al.'' (2003) ''Mycol Res.'' '''107''':901-916. Even though many details of fungal phylogeny remain unresolved, the branches shown here individually appear to have strong support. In a cladogram such as this, the branch lengths are not drawn to any scale of similarity. I have labeled all speciation events so you can refer to these labels in your assignment.]]
+
[[Image:FungiCladogram.jpg|frame|none|Cladogram of fungi studied in the assignments. This cladogram is based on small subunit ribosomal rRNA sequences, and largely follows ''Tehler et al.'' (2003) ''Mycol Res.'' '''107''':901-916. Even though many details of fungal phylogeny remain unresolved, the branches shown here individually appear to have strong support. In a cladogram such as this, the branch lengths are not drawn to any scale of similarity.]]
 +
 
 +
Your species may not be included in this cladogram, but you can easily calculate your own with the following procedure:
 +
 
 +
<div style="padding: 5px; background: #DDDDEE;">
 +
#Access the [http://www.ncbi.nlm.nih.gov/sites/entrez?cmd=retrieve&db=taxonomy NCBI taxonomy database Entrez query page].
 +
#Edit the list of reference species below to include your species and paste it into the form.
 +
 
 +
"Emericella nidulans"[Scientific Name] OR
 +
"Candida albicans"[Scientific Name] OR
 +
"Neurospora crassa"[Scientific Name] OR
 +
"Saccharomyces cerevisiae"[Scientific Name] OR
 +
"Schizosaccharomyces pombe"[Scientific Name] OR
 +
"Ustilago maydis"[Scientific Name]
 +
 
 +
#Next, as '''Display''' option, select '''Common Tree'''.
 +
#Then select the '''phylip tree''' option and click '''save as''' to save the tree in Newick format.
 +
#The output can be edited, and visualized in any program that reads Newick trees.
 +
</div>
 +
 
 +
 
 +
<div style="padding: 5px; background: #E9EBF3;  border:solid 1px #AAAAAA;">
 +
 
 +
===(2.2) Visualizing the APSES domain Phylogenetic Tree===
 +
</div>
 +
 
 +
 
 +
Once Phylip is done calculating the tree, the tree in a text format will be contained in the Phylip <code>outfile</code> - the documentation of what the program has done. Open this textfile for a first look. The tree is complicated and it can look confusing at first. The tree in Newick format is contained in the Phylip file <code>outtree</code>. Visualize it as follows:
 +
 
 +
<div style="padding: 5px; background: #DDDDEE;">
 +
#Open <code>outtree</code> in a texteditor and copy the tree.
 +
#Visualize the tree in alternative representations:
 +
##Navigate to the [http://www.proweb.org/treeviewer/ Proweb treeviewer], paste and visualize your tree.
 +
##Navigate to the [http://www.trex.uqam.ca/index.php?action=newick&project=trex Trex-online Newick tree viewer] for an alternative view. Visualize the tree as a phylogram. You can increase the window height to keep the labels from overlapping.
 +
##In your Jalview window, choose '''File &rarr; Load associated Tree''' and load the Phylip <code>outtree</code> file. You can click into the tree-window to show which clades branch off at what level - it should be obvious that you can identify three major subclades.
 +
##Study the tree: understand what you see and what you would have expected.
 +
</div>
  
In order to study the evolutionary history of the entire gene family you can use the tree you have computed or access the [[APSES_domains_reference_tree|'''APSES domains reference tree''']] here.
+
Here are two principles that will help you make sense of the tree.
  
This is a complicated tree, and it can look impenetrably confusing at first. Here are two principles that will help you make sense of the tree.
 
  
A: '''A gene that is present in an ancestral species, is inherited in all descendent species.''' The gene has to be observed in all OTUs, unless its has been lost (which is a rare event). This means, if a gene is present in two widely divergent species, but in none other of the descendants of the LCA, it is possible that there is some problem with the tree (long branch attraction maybe), or the sequence has been acquired through horizontal gene transfer.
+
A: '''A gene that is present in an ancestral species is inherited in all descendant species'''. The gene has to be observed in all OTUs, unless its has been lost (which is a rare event).
  
B: '''Paralogous genes in an ancestral species should give rise to monophyletic subtrees for each of the genes, in all descendants'''; this means: if the LCA of a branch has e.g. three genes, we would expect three copies of the species cladogram below this branchpoint, one for each of these genes. Each of these subtrees should recapitulate the reference phylogenetic tree of the OTUs, up to the branchpoint of their LCA.
+
B: '''Paralogous genes in an ancestral species should give rise to monophyletic subtrees for each of the paralogues, in all descendants'''; this means: if the LCA of a branch has e.g. three genes, we would expect three copies of the species cladogram below this branchpoint, one for each of these genes. Each of these subtrees should recapitulate the reference phylogenetic tree of the species, up to the branchpoint of their LCA.
  
With these two simple principles (you should draw them out on a piece of paper if they do not seem obvious to you), you can probably pry the [[APSES_domains_reference_tree|reference tree of all APSES domains]] apart quite nicely. A few colored pencils and a printout of the tree will help.
+
 
 +
With these two simple principles (you should draw them out on a piece of paper if they do not seem obvious to you), you can probably pry your tree apart quite nicely. A few colored pencils and a printout of the tree will help.
  
  
Line 184: Line 227:
 
<div style="padding: 5px; background: #E9EBF3;  border:solid 1px #AAAAAA;">
 
<div style="padding: 5px; background: #E9EBF3;  border:solid 1px #AAAAAA;">
  
===(2.1) The Cenancestor's APSES Domains (1 mark)===
+
===(2.1) The Cenancestor's APSES Domains===
 
</div>
 
</div>
  
Refer to your tree or the reference tree for the following two tasks. Be specific, to support your arguments, i.e. use specific branchpoints (by numbers or letters) and OTU or gene names in your arguments (see the example below).
+
Refer to your tree for the following tasks. (Please remember to include your tree in your Assignment submission - it is a result of your computational experiment. Its easiest to copy/paste the tree from the Phylip outfile, rather than copying an image from a Tree viewer). Be specific in your discussion, i.e. refer to specific branchpoints (branchpoints are numbered in the Phylip output) and OTU or gene names in your analysis (see the example below).  
  
&nbsp;<br>
 
&nbsp;<br>
 
<div style="padding: 5px; background: #FFCC99;">
 
;Analysis (1 mark)
 
  
Discuss briefly how many APSES domain proteins the fungal cenancestor appears to have posessed and what evidence you see in the tre that this is so.
+
<div style="padding: 5px; background: #DDDDEE;">
 +
*Consider how many APSES domain proteins the fungal cenancestor appears to have possessed and what evidence you see in the tree that this is so.  
 
</div>
 
</div>
&nbsp;<br>
+
 
&nbsp;
 
  
 
<div style="padding: 5px; background: #E9EBF3;  border:solid 1px #AAAAAA;">
 
<div style="padding: 5px; background: #E9EBF3;  border:solid 1px #AAAAAA;">
Line 209: Line 248:
 
;Analysis (2 marks)
 
;Analysis (2 marks)
  
Assume that the phylogenetic tree for fungi is correct, and that the mixed gene tree is fundamentally correct in its overall arrangement but may have local inaccuracies due to the limited resolution of the method. You have identified the APSES domain genes of the fungal cenancestor above. Apply the expectations we have stated above to discuss briefly through what sequence of duplications and/or gene loss your organism has ended up with the APSES domains it possesses today. Make specific reference to the species tree and either your constructed tree or the [[APSES_domains_reference_tree|reference tree]]. (2 marks)
+
Assume that the cladogram for fungi that I have given above is correct, and that the mixed gene tree you have calculated is fundamentally correct in its overall arrangement but may have local inaccuracies due to the limited resolution of the method. You have identified the APSES domain genes of the fungal cenancestor above. Apply the expectations we have stated above to discuss briefly through what sequence of duplications and/or gene loss your organism has ended up with the APSES domains it possesses today. Make specific reference to the cladogram of species and note in particular in case some of your sequences appear to have been placed into regions of the tree where they don't seem to belong. Also note which branchpoints in the evolutionary history of your sequences correspond to speciations and which ones to duplications.
 +
 
 +
 
 +
Note: A common confusion about cenancestral genes arises from the fact that by far not all expected genes are present in the OTUs. Some will have been lost, some will have been incorrectly annotated in their genome (frameshifts!) and not been found with PSI-BLAST, some may have been missed by you. In general you have to ask: '''given the species represented in a subclade, what is the last common ancestor of that branch'''? The expectation is that '''all''' descendants of that ancestor should be represented in that branch '''unless''' one of the above reasons why a gene might be absent would apply.
 +
 
 +
 
 +
If your species does not have all the genes you would expect it to have inherited from its ancestors, you MUST note that fact and attempt to explain it.
 
</div>
 
</div>
&nbsp;<br>
+
 
&nbsp;
 
  
 
For example the following discusion for ''Saccharomyces cerevisiae'' would be sufficient for full marks:
 
For example the following discusion for ''Saccharomyces cerevisiae'' would be sufficient for full marks:
:(Numbers refer to branchpoints of the mixed gene tree, letters to branchpoints of the species tree). There are four subclades that are shared by most current species, they branch from 129, 108, 76 and (94 + 102). For the latter case, the precise resolution appears not be well resolved, but by comparison with the species tree, we can argue that branch 102 corresponds to branch (H) and should be inserted between branchpoints 94 (corresponding to (A) ) and 96 (B) , not after branch 74. This is because the species under 95 and 102 share a common ancestor (B) that is distinct from 95. ''Saccharomyces cerevisiae'' has one gene in each of these major subclades, there is no gene loss. (Note however that there is no Dikaryomycota (2) orthologue of a Sok2 gene.) ''Saccharomyces cerevisiae'' has an additional paralogue to Sok2 that created the Phd1 gene. This is shared with ''Candida albicans''. There are three possibilites to explain this: (''i'') the gene could have been duplicated before (H) and then lost in separate, independent events after I,J,K,M and N in those species that do not possess an orthologue. (''ii'') the gene could have arisen after (N) or after (K) and then passed by horizontal gene transfer from or to  ''S. cerevisiae'', or ('''iii''') the annotations of orthologues could be incorrect and some of the genes labelled SokA (Sok2 paralogues) could in fact be Phd1 orthologues; if this were the case it would require a reassessment of how much gene-loss would be necessary to explain the subclade below 108.
+
:(Numbers refer to branchpoints of the mixed gene tree, letters to branchpoints of the species tree). I have found five homologues to ''Saccharomyces cerevisiae'' Mbp1 and included them in the mixed gene tree. Two subclades are well defined, and contain all current species, they branch from 41 (Xbp1) and 50 (Sok2/Phd1). The subclade below 6 includes Mbp1 orthologues as well as Swi4 orthologues that do not appear well resolved. Considering only species below the ''saccharomycetales'' branchpoint, I postulate a duplication at that branchpoint that gave rise to yeast Mbp1 and Swi4 since the respective branches contain representatives from all fungi that descended from that branch. There is no good support for the idea that the cenancestor had a Swi4 paralogue. Therefore the cenancestor most likely posessed two paralogues: Mbp1, and Sok2. ''Saccharomyces cerevisiae'' has one gene in each of the major subclades, there is no gene loss. It also has an additional paralogue to Sok2: the Phd1 gene that duplicated at branchpoint 3.  
  
&nbsp;
 
&nbsp;
 
  
 
<div style="padding: 5px; background: #BDC3DC;  border:solid 1px #AAAAAA;">
 
<div style="padding: 5px; background: #BDC3DC;  border:solid 1px #AAAAAA;">
Line 229: Line 271:
 
:* [http://biochemistry.utoronto.ca/undergraduates/courses/BCH441H/restricted/Baldauf_2003_PhylogenyTutorial.pdf '''Review (PDF, restricted)''' Sandra Baldauf: Phylogeny for the Faint of Heart]
 
:* [http://biochemistry.utoronto.ca/undergraduates/courses/BCH441H/restricted/Baldauf_2003_PhylogenyTutorial.pdf '''Review (PDF, restricted)''' Sandra Baldauf: Phylogeny for the Faint of Heart]
 
:* [http://evolution.genetics.washington.edu/phylip.html '''PHYLIP''' home page]
 
:* [http://evolution.genetics.washington.edu/phylip.html '''PHYLIP''' home page]
:* [http://bioweb.pasteur.fr/seqanal/phylogeny/phylip-uk.html '''PHYLIP''' Web Service at the Institut Pasteur]
 
:*[[Assignment_5_fallback_data|'''Fallback data''']]
 
  
;APSES domain alignment
+
;Sequences
:* [[APSES_domains_MUSCLE_revised|All '''APSES domains - MUSCLE aligned''' and sequence names revised]]
+
:* [[Reference APSES domains|Reference APSES domains page]]
 
 
;Tree
 
:*[[APSES_domains_reference_tree|'''APSES domains reference tree''']]
 
 
 
&nbsp;
 
&nbsp;
 
  
 
<div style="padding: 5px; background: #D3D8E8;  border:solid 1px #AAAAAA;">
 
<div style="padding: 5px; background: #D3D8E8;  border:solid 1px #AAAAAA;">
Line 245: Line 279:
 
</div>
 
</div>
  
If you have any questions at all, don't hesitate to mail me at [mailto:boris.steipe@utoronto.ca boris.steipe@utoronto.ca] or post your question to the [mailto:bch441_2008@googlegroups.com Course Mailing List]
+
If you have any questions at all, don't hesitate to mail me at [mailto:boris.steipe@utoronto.ca boris.steipe@utoronto.ca] or post your question to the [mailto:bch441_2011@googlegroups.com Course Mailing List]

Latest revision as of 23:34, 21 September 2012

Note! This assignment is currently active. All significant changes will be announced on the mailing list.

 
 


   

Assignment 4 (last: 2011) - Phylogenetic Analysis

Introduction  

Nothing in Biology makes sense except in the light of evolution.
Theodosius Dobzhansky

... but does evolution make sense in the light of biology?

As we have seen in the previous assignments, the Mbp1 transcription factor has homologues in all other fungi, yet there is not always a clear one-to-one mapping between members of a family in distantly related species. It appears that various systems of APSES domain transcription factors have evolved independently. Of course this bears directly on our notion of function - what it means to say that two genes in different organisms have the "same" function. In case two organisms both have an orthologous gene for the same, distinct function, saying that the function is the same may be warranted. But what if that gene has duplicated in one species, and the two paralogues now perform different, related functions in one organism? Theses two are still orthologues to the other species, but now we expect functionally significant residues to have adapted to the new role of one paralogue. In order to be able to even ask such questions, we need to make the evolutionary history of gene families explicit. This is the domain of phylogenetic analysis. We can ask questions like: how many paralogues did the cenancestor of a clade possess? Which of these underwent additional duplications in the phylogenesis of the organism I am studying? Did any genes get lost? And - adding additional biological insight to the picture - did the observed duplications lead to the "invention" of new biological systems? When was that? And perhaps even: how did the species benefit from this event?


We will develop this kind of analysis in this assignment. In the previous assignment you have established which gene in your species is the reciprocally most closely related orthologue to yeast Mbp1 and you have identified the full complement of APSES domain genes in your assigned organism. In this assignment, we will analyse these genes' evolutionary relationship and compare it to the evolutionary relationship of all fungal APSES domains. The goal is to define families of related transcription factors and their evolutionary history.

A number of excellent tools for phylogenetic analysis exist; general purpose packages include the (free) PHYLIP package and the (commercial) PAUP package. Specialized tools for tree-building include Treepuzzle or Mr. Bayes. This assignment is constructed around programs that are available in PHYLIP, however you are welcome to use other tools that fulfill a similar purpose if you wish. In this field, researchers consider trees that have been built with ML (maximum likelihood) methods to be more reliable than trees that are built with parsimony methods, or distance methods such as NJ (Neighbor Joining). However ML methods are also much more compute-intensive. Just like with multiple sequence alignments, some algorithms will come closer to guessing the truth and others will not and usually it is hard to tell which is the more trustworthy of two diverging results. The prudent researcher tries out alternatives and forms her own opinion. Specifically, we may usually assume results that converge when computed with different algorithms, to be more reliable than those that depend strongly on a particular algorithm, parameters, or details of input data.

However: regarding algorithm and resources, we will take a shortcut in this assignment (something you should not do in real life). We will assume that the tree the algorithm constructs is correct. In "real life" you would establish its reliability with a bootstrap procedure: repeat the tree-building a hundred times with partial data and see which branches and groupings are robust and which depend on the details of the data. In this assignment, we should simply acknowledge that bifurcations that are very close to each other have not been "resolved" and be appropriately cautious in our inferences. In phylogenetic analysis, not all lines a program draws are equally trustworthy. Don't take the trees as a given fact just because a program suggests this. Look at the evidence, include independent information where available, use your reasoning, and analyse the results critically. As you will see, there are some facts that we know for certain: we know which species the genes we have sequenced come from, and we can (usually) make good assumptions about the relationship of the species themselves - the history of speciation events that underlies all evolution of genes. This is extremely helpful information for our work.

Introduction: Tasks

For this assignment, we start from the APSES domains you have collected previously. You will align these domains with a set of reference domains and edit the alignment to make it suitable for phylogenetic analysis, using Jalview. Then you will construct a phylogenetic tree and interpret the tree. The goal is to identify orthologues and paralogues.

In case you want to review concept of trees, clades, LCAs, OTUs and the like, I have linked an excellent and very understandable introduction-level article on phylogenetic analysis (pdf) here and to the resource section at the bottom of this page.

 

Preparation, submission and due date

Read carefully.
Be sure you have understood all parts of the assignment and cover all questions in your answers! Sadly, we always get assignments back in which important aspects have simply overlooked marks unnecessarily. If you did not notice that the above did not make sense, you are reading what you expect, not what is written.

Review the guidelines for preparation and submission of BCH441 assignments.

The due date for the assignment is Monday, November 28 at 12:00 in the morning.

   

Your documentation for the procedures you follow in this assignment will be worth 1 mark.

   

(1) Preparations

   

(1.1) Preparing Input Files

 

For this assignment, we start from the multiple sequence alignments we have constructed previously. We will edit the alignment to make it suitable for phylogenetic analysis. We will construct a phylogenetic tree and we will analyse the tree.

Introduction: Principle

In order to use molecular sequences for the construction of phylogenetic trees, you have to build a multiple alignment first, then edit it. This is important: all rows of sequences have to contain the exact same number of characters and to hold aligned characters in corresponding positions. Phylogeny programs are not meant to revise an alignment but to analyze evolutionary relationships, after the alignment has been determined. The program's inferences are made on a column-wise basis and if your columns contain data from unrelated positions, the inferences are going to be questionable.

The result of the tree construction is a decision about the most likely evolutionary relationships. Fundamentally, tree-construction programs decide which sequences had common ancestors.


Distance based phylogeny programs start by using sequence comparisons to estimate evolutionary distances:

  • they apply a model of evolution such as a mutation data matrix, to calculate a score for each pair of sequences,
  • this score is stored in a "distance matrix" ...
  • ... and used to estimate a tree that groups sequences with close relationships together. (e.g. by using an NJ, Neigbor Joining, algorithm).

They are fast, can work on large numbers of sequences, but are less accurate if genes evolve at different rates.


Parsimony based phylogeny programs build a tree that minimizes the number of mutation events that are required to get from a common ancestral sequence to all observed sequences. They take all columns into account, not just a single number per sequence pair, as the Distance Methods do. For closely related sequences they work very well, but they construct inaccurate trees when they can't make good estimates for the required number of sequence changes.


ML, or Maximum Likelihood methods attempt to find the tree for which the observed sequences would be the most likely under a particular evolutionary model. They are based on a rigorous statistical framework and yield the most robust results. But they are also quite compute intensive and a tree of the size that we are building in this assignment is a challenge for the resources of common workstation (runs about an hour on my computer). If the problem is too large, one may split a large problem into smaller, obvious subtrees (e.g. analysing orthologues as a group, only including a few paralogues for comparison) and then merge the smaller trees; this way even very large problems can become tractable.

ML methods suffer less from "long-branch attraction" - the phenomenon that weakly similar sequences can be grouped inappropriately close together in a tree due to spuriously shared differences.


Clearly, in order for tree-estimation to work, one must not include fragments of sequence which have evolved under a different evolutionary model as all others, e.g. after domain fusion, or after accommodating large stretches of indels. Thus it is appropriate to edit the sequences and pare them down to a most characteristic subset of amino acids. The goal is not to be as comprehensive as possible, but to input those columns of aligned residues that will best represent the true phylogenetic relationships between the sequences.

Introduction: Gaps

Gaps are a real problem here, as usual. Strictly speaking, the similarity score of an alignment program as well as the distance score of a phylogeny program are not calculated for an ordered sequence, but for a sum of independent values, one for each aligned columns of characters. The order of the columns does not change the score. However in an optimal sequence alignment with gaps, this is no longer strictly true since a one-character gap creation has a different penalty score than a one-character gap extension! Most alignment programs use a model with a constant gap insertion penalty and a linear gap extension penalty. This is not rigorously justified from biology, but parametrized (or you could say "tweaked") to correspond to our observations. However, most phylogeny programs, (such as the programs in PHYLIP) do not work in this way. PHYLIP strictly operates on columns of characters and treats a gap character just like a residue with the one letter code "-". Thus gap insertion- and extension- characters get the same score. For short indels, this underestimates the distance between pairs of sequences, since any evolutionary model should reflect the fact that gaps are much less likely than point mutations. If the gap is very long though, all events are counted individually as many single substitutions (rather than one lengthy one) and this overestimates the distance. And it gets worse: long stretches of gaps can make sequences appear similar in a way that is not justified, just because they are identical in the "-" character. It is therefore common and acceptable to edit gaps in the alignment and delete all but one or two columns of gapped sequence, or to remove such columns altogether.


Introduction: The outgroup

To analyse phylogenetic trees it is useful (and for some algorithms required) to define an outgroup, a sequence that presumably diverged from all other sequences in a clade before they split up among themselves. Wherever the outgroup inserts into the tree, this is the root of the rest of the tree. And whenever a molecular clock is assumed, the branching point that connects the outgroup can be assumed to be the oldest divergence event. I have defined an outgroup sequence and added it to the reference APSES domains page. The procedure is explained in detail on that page.

>gi|301025594|ref|ZP_07189117.1| KilA-N domain protein [Escherichia coli MS 69-1]
MTSFQLSLISREIDGEIIHLRAKDGYINATSMCRTAGKLLSDYTRLKTTQEFFDELSRDMGIPISELIQS
FKGGRPENQGTWVHPDIAINLAQWLSPKFAVQVSRWVREWMSGERTTAEMPVHLKRYMVNRSRIPHTHFS
ILNELTFNLVAPLEQAGYTLPEKMVPDISQGRVFSQWLRDNRNVEPKTFPTYDHEYPDGRVYPARLYPNE
YLADFKEHFNNIWLPQYAPKYFADRDKKALALIEKIMLPNLDGNEQF

E. coli KilA-N protein. Residues that do not align with APSES domains are shown in grey.

Preparing APSES sequences
  1. Navigate to the reference APSES domains page and copy the sequences.
  2. Open Jalview, select File → Input Alignment → from Textbox and paste the sequences into the textbox.
  3. Add the APSES domain sequences from your species that you have defined in the previous assignment.
  4. When all the sequences are present, click on New Window.
  5. In Jalview, select Web Service → Alignment → MAFFT Multiple Sequence Alignment. The alignment is calculated in a few minutes and displayed in a new window.
  6. Choose any colour scheme and add Colour → by Conservation. Adjust the slider left or right to see which columns are highly conserved.
  7. Save the alignment as a Jalview project before editing it for phylogenetic analysis. You may need it again.


Introduction: Alignment editing for phylogenetic reconstruction

In practice, follow the fundamental principle that all characters in a column should be related by homology. This implies the following rules of thumb:

  • Remove all stretches of residues in which the alignment appears ambiguous (not just highly variable, but ambiguous regarding the aligned positions).
  • Remove all frayed N- and C- termini, especially regions in which not all sequences that are being compared appear homologous and that may stem from unrelated domains.
  • Remove all gapped regions that appear to be alignment artefacts due to inappropriate input sequences.
  • Remove all but approximately one column from gapped regions in those cases where the presence of several related insertions suggest that the indel is real, and not just an alignment artefact. (Some researchers simply remove all gapped regions).
  • Remove sections N- and C- terminal of gaps where the alignment appears questionable.
  • Also, consider that neither residues that are completely different between all species, nor residues that are completely conserved are informative for relationship distances.
  • If your sequences are too long, your tree calculations may run out of memory. 60-80 aligned residues should be plenty and if the sequences fit on a single line you will save yourself potential trouble with block-wise vs. interleaved input.If you do run out of memory try removing columns of sequence.
  • Move the KilA-N outgroup sequence to the first line of your alignment, since this is where PHYLIP will look for it by default.


(Possible) steps in editing a multiple sequence alignment towards a PHYLIP input file. a: raw alignment (CLUSTAL format); b: sequences assembled into single lines; c: columns to be deleted highlighted in red - 1, 3 and 4: large gaps; 2: uncertain alignment and 5: frayed C-terminus: both would put non-homologous characters into the same column; d: input data for PHYLIP: names for sequences must not be longer than 10 characters, the first line must contain the number of sequences and the sequence length. PHYLIP is very picky about incorrectly formatted input, read the PHYLIP sequence format guide.
Once you are satisfied with your editing, proceed as follows
  1. Download the PHYLIP package from the Phylip homepage and install it on your computer.
  2. Prepare a PHYLIP input file from your Jalview alignment. The simplest way to achieve this appears to be:
    1. In Jalview, use File → Output to Textbox→FASTA, then Edit→Select All and Edit→copy the sequences.
    2. In a browser, navigate to the Readseq sequence conversion service.
    3. Paste your sequences into the form and choose Phylip as the output format. Click on submit.
    4. Save the resulting page as a text file in the directory where the phylip executables reside on your computer. Give it some useful name such as All-APSES_domains.phy.
  3. Make a copy of that file and name it infile. Note: make sure that your Microsoft Windows operating system does not silently append the extension ".txt" to your file. It should be called "infile", nothing else and you should never, never, ever permit your operating systems to slyly hide file extensions from you when it displays filenames. You have been warned.


(1.2) Calculating a Tree

 
 

  • Use the proml program of PHYLIP (protein sequences, maximum likelihood tree) to calculate a phylogenetic tree. Use the default parameters except that you must change option S: Speedier but rougher analysis? to No - your analysis should not sacrifice accuracy for speed. The calculation will take a while.

 
 

(2) Analysis (2 marks)

I have constructed a cladogram for the species we are analysing, based on data published for 1551 fungal ribosomal sequences. Such reference tres from rRNA data are a standard method of phylogenetic analysis, supported by the assumption that rRNA sequences are monophyletic and have evolved under comparable selective pressure in all species.

Cladogram of fungi studied in the assignments. This cladogram is based on small subunit ribosomal rRNA sequences, and largely follows Tehler et al. (2003) Mycol Res. 107:901-916. Even though many details of fungal phylogeny remain unresolved, the branches shown here individually appear to have strong support. In a cladogram such as this, the branch lengths are not drawn to any scale of similarity.

Your species may not be included in this cladogram, but you can easily calculate your own with the following procedure:

  1. Access the NCBI taxonomy database Entrez query page.
  2. Edit the list of reference species below to include your species and paste it into the form.
"Emericella nidulans"[Scientific Name] OR
"Candida albicans"[Scientific Name] OR
"Neurospora crassa"[Scientific Name] OR
"Saccharomyces cerevisiae"[Scientific Name] OR
"Schizosaccharomyces pombe"[Scientific Name] OR
"Ustilago maydis"[Scientific Name]
  1. Next, as Display option, select Common Tree.
  2. Then select the phylip tree option and click save as to save the tree in Newick format.
  3. The output can be edited, and visualized in any program that reads Newick trees.


(2.2) Visualizing the APSES domain Phylogenetic Tree


Once Phylip is done calculating the tree, the tree in a text format will be contained in the Phylip outfile - the documentation of what the program has done. Open this textfile for a first look. The tree is complicated and it can look confusing at first. The tree in Newick format is contained in the Phylip file outtree. Visualize it as follows:

  1. Open outtree in a texteditor and copy the tree.
  2. Visualize the tree in alternative representations:
    1. Navigate to the Proweb treeviewer, paste and visualize your tree.
    2. Navigate to the Trex-online Newick tree viewer for an alternative view. Visualize the tree as a phylogram. You can increase the window height to keep the labels from overlapping.
    3. In your Jalview window, choose File → Load associated Tree and load the Phylip outtree file. You can click into the tree-window to show which clades branch off at what level - it should be obvious that you can identify three major subclades.
    4. Study the tree: understand what you see and what you would have expected.

Here are two principles that will help you make sense of the tree.


A: A gene that is present in an ancestral species is inherited in all descendant species. The gene has to be observed in all OTUs, unless its has been lost (which is a rare event).

B: Paralogous genes in an ancestral species should give rise to monophyletic subtrees for each of the paralogues, in all descendants; this means: if the LCA of a branch has e.g. three genes, we would expect three copies of the species cladogram below this branchpoint, one for each of these genes. Each of these subtrees should recapitulate the reference phylogenetic tree of the species, up to the branchpoint of their LCA.


With these two simple principles (you should draw them out on a piece of paper if they do not seem obvious to you), you can probably pry your tree apart quite nicely. A few colored pencils and a printout of the tree will help.


   


(2.1) The Cenancestor's APSES Domains

Refer to your tree for the following tasks. (Please remember to include your tree in your Assignment submission - it is a result of your computational experiment. Its easiest to copy/paste the tree from the Phylip outfile, rather than copying an image from a Tree viewer). Be specific in your discussion, i.e. refer to specific branchpoints (branchpoints are numbered in the Phylip output) and OTU or gene names in your analysis (see the example below).


  • Consider how many APSES domain proteins the fungal cenancestor appears to have possessed and what evidence you see in the tree that this is so.


(2.2) Unraveling your organism's APSES domains (2 marks)

 
 

Analysis (2 marks)

Assume that the cladogram for fungi that I have given above is correct, and that the mixed gene tree you have calculated is fundamentally correct in its overall arrangement but may have local inaccuracies due to the limited resolution of the method. You have identified the APSES domain genes of the fungal cenancestor above. Apply the expectations we have stated above to discuss briefly through what sequence of duplications and/or gene loss your organism has ended up with the APSES domains it possesses today. Make specific reference to the cladogram of species and note in particular in case some of your sequences appear to have been placed into regions of the tree where they don't seem to belong. Also note which branchpoints in the evolutionary history of your sequences correspond to speciations and which ones to duplications.


Note: A common confusion about cenancestral genes arises from the fact that by far not all expected genes are present in the OTUs. Some will have been lost, some will have been incorrectly annotated in their genome (frameshifts!) and not been found with PSI-BLAST, some may have been missed by you. In general you have to ask: given the species represented in a subclade, what is the last common ancestor of that branch? The expectation is that all descendants of that ancestor should be represented in that branch unless one of the above reasons why a gene might be absent would apply.


If your species does not have all the genes you would expect it to have inherited from its ancestors, you MUST note that fact and attempt to explain it.


For example the following discusion for Saccharomyces cerevisiae would be sufficient for full marks:

(Numbers refer to branchpoints of the mixed gene tree, letters to branchpoints of the species tree). I have found five homologues to Saccharomyces cerevisiae Mbp1 and included them in the mixed gene tree. Two subclades are well defined, and contain all current species, they branch from 41 (Xbp1) and 50 (Sok2/Phd1). The subclade below 6 includes Mbp1 orthologues as well as Swi4 orthologues that do not appear well resolved. Considering only species below the saccharomycetales branchpoint, I postulate a duplication at that branchpoint that gave rise to yeast Mbp1 and Swi4 since the respective branches contain representatives from all fungi that descended from that branch. There is no good support for the idea that the cenancestor had a Swi4 paralogue. Therefore the cenancestor most likely posessed two paralogues: Mbp1, and Sok2. Saccharomyces cerevisiae has one gene in each of the major subclades, there is no gene loss. It also has an additional paralogue to Sok2: the Phd1 gene that duplicated at branchpoint 3.


(3) Summary of Resources

 

Links
Sequences

[End of assignment]

If you have any questions at all, don't hesitate to mail me at boris.steipe@utoronto.ca or post your question to the Course Mailing List