Lab 3, RGGS 670: Algorithmic Approaches to Biological Data, Spring 2016

Turtle Directions

Today's lab works through two examples of "looping through strings." For the first example, we will use the following abbreviations to give directions to our turtles:

F: move forward one square
R: turn right 90 degrees
L: turn left 90 degrees
U: lift up pen (turtle can still move but does not draw)
D: put the pen down (the turtle draws its path again)

For example, "RRFRFFFLFFLFFFFFF" is the path on the left:

What set of directions created the path on the right?

Let's create a program to test this by drawing out paths, given a set of directions. A possible outline for the program is: For each character in the directions:

if the character is 'F', move your turtle forward. if the character is 'L', turn your turtle left. if the character is 'R', turn your turtle right. if the character is 'U', lift up the pen. if the character is 'D', put the pen down.

To turn this into Python code, we need to give names to variables we are using. Lets call the string of directions, directions and use c as our loop index:

directions = "RRFRFFFLFFLFFFFFF"

for c in directions:

The rest of the loop can be done using decisions (remember to use "==" for comparison):

    if c == 'F':
        tess.forward(30)
    if c == 'L':
        tess.left(90)
    ...

Since we only go to the second if-statement if the test on the first one fails (i.e. only check if the character is 'L' if we already checked and it wasn't 'F'), we can also write this as:

    if c == 'F':
        tess.forward(30)
    elif c == 'L':
        tess.left(90)
    ...

The looping and decisions are the hardest part of the program, but we need a few more pieces to make it run:

Remember to import the turtle library.
You need to construct a turtle to do the drawing for you.
End the program with an turtle.exitonclick() so that the program doesn't spin its wheels at the end.

Test your program on several sets of directions to make sure it works.

Drawing Phylogenetic Trees

A common use of trees is to represent the family history of a set of species. For example, this cladogram represents some of the species found in the Halls of Dinosaurs. Ornithomimids and Maniraptors are "siblings" in this tree, and Carnosaurs are their cousins.

A compact way to represent trees is via the Newick format. This format groups siblings, then cousins, etc. For the dinosaurs, we would group (Ornithomimids, Maniraptors). The next most closely related species are the Carnosaurs. This can be represented as: (Carnosaurs, (Ornithomimids, Maniraptors)). The whole tree of the 9 species is (using only the first 3 letters of each name to save space): ((Sau, (Cer, (Car, (Orn, Man)))), (Leso,(Thy, (Eru, Mar)))).

In pairs, design a program that uses turtles to draw trees, using turtles. Draw out a couple of simple ones, looking just at the string:

(Ape, (Baboon, Chimp))
((Ape, Baboon), Chimp)
(1,(2,(3,(4,(5,(6,(7,8)))))))
((x,y), ((u,v),w))

What should be drawn when you see a

'('
')'
','
name (for this lab, we'll limit the names to single characters to make it easier to parse)

Challenges

Write a program that will draw out trees given the Newick format. Computer scientists draw their trees with the roots in the air, biologists draw trees with roots in the ground, and folks in between often draw the trees sideways to avoid arguments. Modify your program to draw your trees sideways.
If you used fixed angles for your branches (i.e. the left child is always 60 degrees from the right child), then as you have more and more descendants they start drawing over each other. How can you squeeze in more nodes at each level?
(Optional): The nodes in our trees had at most 3 neighbors (usually a parent and two children)-- called `binary trees' (computer science) or `fully resolved' (biology). How could we represent and draw non-binary trees or trees with polytomies?
(Optional): If you read in a tree in Newick format, can you design a program that says its height (the longest path from the root to a leaf) without drawing it?

Lab Report

For each lab, you should submit a lab report by the target date to: kstjohn AT amnh DOT org. The reports should be about a page for the first labs and contain the following:

Target Date: 17 February 2016
Title: Lab 3:
Name & Email:

Purpose: Give summary of what was done in this lab.
Procedure: Describe step-by-step what you did (include programs or program outlines).
Results: If applicable, show all data collected. Including screen shots is fine (can capture via the Grab program).
Discussion: Give a short explanation and interpretation of your results here.