In this project, you will develop an application that allows a geneticist to compare two strands of DNA for similarity.
Scientists measure how closely related two species are by looking at the DNA sequences for key proteins and seeing how similar or dissimilar they are. The process of sequence alignment arranges two or more DNA sequences so that corresponding nucleotides in the sequences can be compared; the more nucleotides that match between the sequences, the closer we say the two sequences are evolutionarily.
Consider the two strings of DNA below, where matching nucleotides are underlined
Species 1: AATAACGAAA
Species 2: AAAACGAAAA
We would say that these two DNA sequences have 6 matching positions and 4 mismatches, perhaps suggest- ing that the two species are not closely related. Every corresponding position that are equal is a match, and all others are mismatches.
Of course, DNA changes over time with reproduction and evolution, and so even two very similar species may have mis-matched DNA sequences due to the random insertion, removal, or mutation of one nucleotide. If a scientist supposes that these two species are more closely related than it appears, they can change the alignment of the two DNA sequences by inserting an indel, which is a placeholder that represents some missing nucleotide, and is always counted as a mismatch. Playing with alignments can reveal that two species are actually very closely related despite initial appearances.
Reconsider the two species from before. A scientist places an indel (shown as a dash (-)) at the end of Species 1, and at character position 3 (using the biology standard of starting at position 1, not the comput- ing standard of starting at 0) in Species 2. Check out the alignment now:
Species 1: AATAACGAAA-
Species 2: AA-AACGAAA
Only two mismatches in the sequences! Our scientist could use this as evidence that a single change occurred in each species' DNA sequence for this protein, and that change accounts for the di erences in the expression of that protein in each species.
1 This assignment is based on the work of Bill Punch and Richard Enbody at Michigan State University. CC BY-SA.
While complex algorithms exist to do sequence alignment, it is also useful to allow a researcher to perform alignments by hand.
Positions vs. indexes:
In this document, the words position and index both refer to one particular spot in a string; when
index is used, it is implied to be 0-based ( rst character is index 0), whereas when position is used, the implication is 1-based ( rst character is at position 1).
The overal goal for this project is to allow a user to enter two DNA sequence strings. The program will then enter a main menu loop where the user will be given many options to manipulate the two strings. One option will add an indel to a string, another will remove it. A third option will print a similarity score for the two strings, summarizing how many positions were matching. A fourth option will suggest where to add an indel to maximize the number of matches.
As in the previous project, you will develop your solution in two milestones. The menu itself will be part of Milestone 2; in Milestone 1 you will work on gathering input and scoring the similarity of those inputs. You will break your solution into functions de ned below, and test cases will make sure you follow the requirements of each function, as well as the overall application itself.
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of