4003-532/4005-736 Parallel Computing II
Module 3 Lecture Notes -- Phylogenetic Trees
Exhaustive Search
Prof. Alan Kaminsky
Rochester Institute of Technology -- Department of Computer Science
Exhaustive Search Program
- Approach
- Input S DNA sequences
- Excise uninformative sites
- Generate all (2S - 3)!! phylogenetic trees
- Compute parsimony score (number of state changes) of each tree using the Fitch algorithm
- Output tree(s) with the best (smallest) score
- Tree generation algorithm
- Depth-first search of the space of phylogenetic trees
- Depth-first search of the space of phylogenetic trees
- Package edu.rit.phyl.pars
- Class DnaSequence -- source code
- Class DnaSequenceList -- source code
- Class DnaSequenceTree -- source code
- Class DnaSequenceTreeList -- source code
- Class MaxParsExh -- source code
Example 1
- Sequence data supplied by Prof. Larry Buckley, RIT Department of Biology
- 16 iguana species, 375 sites, 17 informative sites
- Input file: iguana16.phy
16 375 DipsosauruTGCAGTAAGAACAGTTTGGCATCACGGCAGAGTTTCTGGTCAGAATTAAATGTGGCACAT BrachylophTGCAGTAAGAACAGTTTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT Cyclura_caTGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT I_iguana_6TGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT S_obesus_1TGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT AmblyrynchTGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAACTAAACGTGGCACAT ConolophusTGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT C_pectinatTGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT C_defensorTGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT C_clarki_7TGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT C_similis_TGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT C_h_macrolTGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT C_flavidorTGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT C_bakeri_4TGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT C_melanostTGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT Cy_r_rileyTGCAGTAAGAACAGTCTGGCATCACGGCAGAGTTTCTGGGCAGAATTAAACGTGGCACAT
- Last phylogenetic tree generated by the MaxParsExh program for different numbers of sequences
- *Score = Parsimony score (number of state changes)
- **Time = Running time (msec) on tardis.cs.rit.edu
# Seq. Score* Tree Time** 3 31 
114 4 34 
108 5 36 
117 6 42 
134 7 42 
189 8 46 
302 9 48 
1558 10 55 
24718 11 57 
485534
Example 2
- Sequence data supplied by Prof. Larry Buckley, RIT Department of Biology
- 18 iguana species, 900 sites, 274 informative sites
- Input file: iguana18.phy
18 900 SOOBESUS16ACTCATCGACCTACCCGCCCCCTCCAATATTTCTGCATGATGAAACTTCGG SOTOWNSE22................................................... SOTUMIDU18................................................... SOOBESUS07.T......................T.....C.................... SHISPIDUS1.T............................C.................... SAVARIUS06.T............................C.................... SAUSTRALI9.T..........G........T........C...........G........ SAKLAUBE10.T..............A....T........C...........G........ SASLEVIN13.T..............A..........C..C...........G........ IGIGUANA23.T..........G..............C..C.................... CSIMILIS25.T..........C..AA....A.....C..C.................... CTHEMCONS1.T..............A.......T..C..C..C................. CTHEMCONS2.T..............A.......T..C..C..C................. CYNUBILA27.T..........G..AA....A.....C..C..CT.T.............. DDORSALI28.T....T.....T..A.....A..A..C.................T..T.. BFASCIAT29CT.G..T.....G..AA.G........C..C.....G..G........... CSUBCRIS26.T....T........AA.......T..C..C..C.....G........... OQUADRIM30.T....T.....T..AA....A..A.....C..A..............T..
- Last phylogenetic tree generated by the MaxParsExh program for different numbers of sequences
- *Score = Parsimony score (number of state changes)
- **Time = Running time (msec) on tardis.cs.rit.edu
# Seq. Score* Tree Time** 3 43 
148 4 81 
141 5 96 
153 6 111 
184 7 136 
344 8 150 
688 9 167 
4645 10 259 
82676 11 331 
1926761
| Course Page |
| Home Page |