CSE 231 Spring 2025
Computer Project #4
1. Learning objectives
This assignment focuses on the design, implementation and testing of a Python program that uses character
strings for looking at the DNA sequences for key proteins and seeing how similar/dissimilar they are. This
assignment will give you more experience in the use of:
1. Functions
2. Strings manipulation and methods
3. Conditionals and Iterations
4. input/output
Prohibitions:
1. You are NOT allowed to import any module.
2. You are NOT allowed to use any advanced data structures such as lists, Tuples, Sets, Dictionaries,
Classes, etc. Use of these prohibited concepts earns zero points for the whole project.
3. You are NOT allowed to use global variables.
4. You are NOT allowed to use string.split()
5. You are ONLY allowed to use the string methods .upper(), .lower(), .find(),
.strip(), .replace()
2. Important Note about submission
3. Assignment Deliverable
• We provide a zip file on the course website that you need to download into your computer, unzip the
file, and open it in PyCharm (similar to the lab) to access the starter code.
• Every project has a video and a document to get you started with the project. The video is posted on the
same page of the course website as the instructions. Watch the project video for more help with the
problem-solving part.
• To finalize and submit your code:
1- Click on the assignment link in D2l for the first time.
2- Write or copy your code in CODIO in the tab named proj04.py
3- Click on the button “Code Co@ch Buddy”. This will grade your assignment. Then, a window
appears with your grade information. Expand the window to see the details and explanations. Click
This assignment is worth 40 points (4.0% of course grade), and must be completed before 11:59 PM
EST on Monday, February 17th.
After the due date, your score will be deducted by 2% for every 1 hour late or a fraction of it. No
submissions will be accepted after 24 hours from the due date. The penalty will be applied on the
full project score.
The project will be automatically submitted by the due date (02/17). If you want to keep working on it
after the deadline with penalty, you must manually click on “Mark as uncompleted”, acknowledge the
penalty message, then refresh the page. Please manually click on “Mark as completed” when done to
avoid any unnecessary penalty.
on the links (pink or blue) to get feedback on your assignment. You can then use the feedback to
improve your grade.
4- Once you are satisfied with your work, make sure to click on “Mark as Completed” to submit your
code and avoid any late penalties.
4. Assignment Background
In the field of genomics and bioinformatics, researchers analyze
vast amounts of DNA sequence data to study genetic variations,
identify mutations, and advance medical research. However, the
sheer volume of genetic data presents significant challenges in
storage, transmission, and computational processing.
Genomic sequences can be millions to billions of base pairs
long, and transferring this data across research institutions,
hospitals, and cloud databases requires efficient compression
and alignment techniques to reduce storage costs and speed up
computational analysis.
In Project 04, we are going to revisit Project 03. We are going
to start by modifying the project to use functions. Then, we will
add some other features like DNA sequence compression. To
summarize, your task is to develop a Python-based algorithm
that does DNA sequence data compression and alignment.
Below are some backgrounds about the DNA sequence data compression task that you are required to do.
4.1 DNA Sequence Compression
DNA sequence compression helps identify repeating patterns, which can indicate gene duplications
important for studying evolution, repetitive elements like short tandem repeats (STRs) used in forensic
DNA analysis, and genome-wide mutations that may be linked to diseases. By detecting redundant regions,
compression techniques allow researchers to focus on unique genetic variations, making genetic analysis
more efficient and insightful.
DNA sequence is compressed by identifying repeated substrings and replacing them with backward
references in the format (start_position, length). This helps reduce redundancy in long
sequences. Below are some examples of compression processes. You should watch the project video for
more help with the problem-solving part.
Example 0 Compression Process:
DNA Sequence: AACGTACGTAT
Compressed DNA: AACGT(1,4)AT
• The substring "ACGT" (at position 1) is repeated at position 5.
The second occurrence is replaced with a reference to its first occurrence:
It is replaced with (1,4), meaning "copy 4 characters from position 1."
Example 1 Compression Process:
DNA Sequence: AATGCGTACGTACGTGCGT
Compressed DNA: AATGCGTA(4,4)CG(2,5)
• The substring "CGTA" (at position 4) is repeated at position 8.
The second occurrence is replaced with a reference to its first occurrence:
It is replaced with (4,4), meaning "copy 4 characters from position 4."
• The substring "TGCGT" (at position 2) is repeated at position 14.
The second occurrence is replaced with a reference to its first occurrence:
It is replaced with (2,5), meaning "copy 5 characters from position 2."
Example 2 Compression Process:
DNA Sequence: ACGTACGTACGTACGTACGT
Compressed DNA: ACGT(0,4)(0,8)(0,4)
• The substring "ACGT" (at position 0) is repeated at position 4.
The second occurrence is replaced with a reference to its first occurrence:
It is replaced with (0,4), meaning "copy 4 characters from position 0."
• The substring "ACGTACGT" (at position 0) is repeated at position 8.
The second occurrence is replaced with a reference to its first occurrence:
It is replaced with (0,8), meaning "copy 8 characters from position 0."
• The substring "ACGT" (at position 0) is repeated at position 16.
The second occurrence is replaced with a reference to its first occurrence:
It is replaced with (0,4), meaning "copy 4 characters from position 0."
5. Assignment Specifications
5.1 General Requirements
These are general requirements that you need to satisfy to ensure a full score:
1. Coding Standards will be enforced for this project (Check which ones are appropriate):
http://www.cse.msu.edu/~cse231/General/coding.standard.html
Auto-grader on Codio provides you with feedback on your code about all the specifications you need for
the full score.
2. Per the syllabus, if you "hard code" answers, you will receive a grade of zero for the whole project.
3. You should only use materials covered in class up to week 4 (videos and textbook).
4. There must be at least 9 functions in a meaningful way.
a. A good practice is to have functions that perform one task at a time. It makes your code more
readable.
b. Non-used functions won’t be counted.
c. There must be a function named main()(check section 5.2 for more details about the
assignment specifications). The main function is called by the following 2 lines that should not
be modified or removed:
d. There must be at least 7 other functions that do something meaningful (you can have more
functions). For example, have a function for each option (see details below).
5.2 Specific requirements
Your task is to implement a DNA sequence analysis tool that following operations. The available commands are
as follows:
A. DNA Sequence Alignment
C. DNA Sequence Compression
H. Display the menu of options.
X. Exit.
So, you may already guess what we want to do.
Your program will:
1. Display the banner. We provide this variable in the starter code.
2. Display the menu. We provide this variable in the starter code.
3. Prompt for a choice from the menu.
4. Based on the user choice, do DNA Sequence Alignment, DNA Sequence Compression or
display the menu. Your code should be able to handle lowercase and uppercase menu choice.
5. The menu should be displayed only at the beginning, when the user enters an invalid menu option, or
when the user wants to display the menu (option "H").
6. Prompt the user if they want another operation.
7. If the user chooses not to do another operation (option "X"). The program should display the goodbye
message.
A. DNA Sequence Alignment: (similar to project 3 but with functions)
1. You will prompt for two strings. To be biologically correct, the string should not be empty and the
characters in the strings should consist of only: "A", "T", "C", "G". The strings do not have to be of the
same length. When the user enters an invalid string, the program will display an appropriate error
message and prompt again until a string is input.
2. You will then prompt for one of 3 commands:
o "a" for add. Add an indel
o "d" for delete. Delete an indel
o "s" for score. Score the present alignment
o "q" for quit. Stop the process.
• Adding an Indel. When you add an indel, you must prompt for two pieces of information:
o which string to change. No error checking is needed
o at what index (starting at 0) do you wish to place the indel (placement is before the given
index, Error if the index is out of range).
o The string should then be modified and a dash (-) added.
if __name__ == '__main__':
main()
• Delete an Indel: If you can add an indel, you should be able to delete it if it doesn't do what you
want. Again, you must prompt for two pieces of information:
o which string to change. No error checking is needed
o the index (starting at 0) to delete the indel. It is an Error to delete a character that is not an
indel. Also, Error if the index is out of range).
o The string should then be modified and the dash (-) is removed.
• Scoring. You will report the number of matches and the number of mismatches.
o If one string is shorter than the other, the shorter string is filled out with indels.
o Any indel is automatically a mismatch.
o After you score, you print both strings.
Matching characters are printed in lower case. If the user entered upper case letters,
you convert them to lower case on a match.
All mismatches are printed in upper case.
Indels are printed as dashes.
o This option does not modify the original strings. These modifications should only be
displayed.
B. DNA Sequence Compression:
1. The program will prompt for a string DNA sequence to compress. The string should not be empty and
the characters in the strings should consist of only: "A", "T", "C", "G". Uppercase, lowercase, or a mix
of cases characters are all accepted.
2. Detect repeating substrings within a DNA sequence similar to the example provided in section 4.1
3. Replace long repeated patterns (length > 3) with a reference notation (start_index, length).
4. When searching for a pattern lowercase and uppercase letters should be treated the same.
5. Display the original DNA sequence, as well as the compressed DNA sequence. Both strings are printed
using upper case letters. You can find the formatted messages in Codio as well as the mentioned zip file,
on the webpage. A sample interaction comes at the end of the document.
6. Assignment Notes
1. You must NOT use lists to complete this project. This includes string.split().
2. To clarify the project specifications, sample output is provided at the end of this document.
3. The coding standard for CSE 231 is posted on the course website:
http://www.cse.msu.edu/~cse231/General/coding.standard.html
4. Items 1-7 of the Coding Standard will be enforced for this project.
7. Suggested Procedure
• Solve the problem using pencil and paper first. You cannot write a program until you have figured out
how to solve the problem. This first step can be done collaboratively with another student. However,
once the discussion turns to Python specifics and the subsequent writing of Python statements, you must
work on your own.
• Edit your program to add new capabilities one at a time.
• Divide-and-conquer is a good approach. Complete the program for one command at a time. Here you
can have a separate function for most commands and have a function for a given operation and use it
throughout your code. Some of the commands are similar. You can partially modify the related
functions and get them to work for another command.
• Start with a main loop. Prompt before the loop and test that the loop stops when ‘X’ is entered and
similarly complete the operation for each command. Test it, when it is done, then move to the operation
of another command.
• As before, try to do this in pieces:
o get the command loop working
o get individual commands to work (scoring is the most work, save it till last)
o Printing the string is best done by creating a new string and adding characters (upper, lower or
dashes) to that string and then printing it. Then clear it before the next printing.
• Be sure to use the Codio system to submit the final version of your program.
8. Grading Rubric
Computer Project #04 Scoring Summary
General Requirements:
(5 pts) Coding Standard
(14 pts) At least 7 function definitions
Implementation: 21 points total.
Test Case 0:
Test Case 1:
Test Case 2:
Test Case 3:
Tests 2 and 3 are hidden. More points are allocated to the hidden tests. The
visible tests serve as a self-check. To pass all tests, you need to follow the
complete instructions in the PDF.
9. Sample Output
Test 0 (No errors)
============================================
PROJECT HELIX: DNA ALIGNMENT
============================================
🧬🧬 Optimizing DNA Storage & Transmission
🚀🚀 Accelerating Bioinformatics Research
A--T C--G G--C T--A A--T G--C
| | | | | |
T--A G--C C--G A--T T--A C--G
============================================
Please choose one of the options below:
A. DNA Sequence Alignment
C. DNA Sequence Compression
H. Display the menu of options.
X. Exit.
:~Enter option ~:a
:~Input String 1 ~:aaatttccc
:~Input String 2 ~:aatttcccc
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:s
Matches: 7 Mismatches: 2
String 1: aaAttTccc
String 2: aaTttCccc
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:a
:~Work on which string (1 or 2) ~:2
:~Before what index ~:2
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:s
Matches: 8 Mismatches: 2
String 1: aaAtttccc String 2: aa-tttcccC
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:D
:~Work on which string (1 or 2) ~:2
:~Delete what ~:2
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:s
Matches: 7 Mismatches: 2
String 1: aaAttTccc
String 2: aaTttCccc
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:q
:~Enter option ~:H
Please choose one of the options below:
A. DNA Sequence Alignment
C. DNA Sequence Compression
H. Display the menu of options.
X. Exit.
:~Enter option ~:c
:~Enter DNA sequence ~:aacgtacgtat
Original DNA Sequence:
AACGTACGTAT
Compressed DNA Sequence:
AACGT(1,4)AT
:~Enter option ~:C
:~Enter DNA sequence ~:AATGCGTACGTACGTGCGT
Original DNA Sequence:
AATGCGTACGTACGTGCGT
Compressed DNA Sequence:
AATGCGTA(4,4)CG(2,5)
:~Enter option ~:X
Exiting program...
Beware of computational biologist they screw genes and protein!
Test 1 (Error checking)
============================================
PROJECT HELIX: DNA ALIGNMENT
============================================
🧬🧬 Optimizing DNA Storage & Transmission
🚀🚀 Accelerating Bioinformatics Research
A--T C--G G--C T--A A--T G--C
| | | | | |
T--A G--C C--G A--T T--A C--G
============================================
Please choose one of the options below:
A. DNA Sequence Alignment
C. DNA Sequence Compression
H. Display the menu of options.
X. Exit.
:~Enter option ~:a
:~Input String 1 ~:aaabbbccc
Invalid characters in the DNA sequence
:~Input String 1 ~:aaaZBb-ccc
Invalid characters in the DNA sequence
:~Input String 1 ~:AATAACGAAA
:~Input String 2 ~:AZXTCGATAA
Invalid characters in the DNA sequence
:~Input String 2 ~:AAAACGAAAA
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:s
Matches: 6 Mismatches: 4
String 1: aaTaACGaaa
String 2: aaAaCGAaaa
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:a
:~Work on which string (1 or 2) ~:2
:~Before what index ~:10
Insert index out of range
:~Before what index ~:2
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:s
Matches: 9 Mismatches: 2
String 1: aaTaacgaaa String 2: aa-aacgaaaA
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:z
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:d
:~Work on which string (1 or 2) ~:1
:~Delete what ~:2
Not an indel
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:d
:~Work on which string (1 or 2) ~:2
:~Delete what ~:15
Delete index out of range
:~Delete what ~:2
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:s
Matches: 6 Mismatches: 4
String 1: aaTaACGaaa
String 2: aaAaCGAaaa
:~What do you want to do:
a (add indel)
d (delete indel)
s (score)
q (quit) ~:q
:~Enter option ~:h
Please choose one of the options below:
A. DNA Sequence Alignment
C. DNA Sequence Compression
H. Display the menu of options.
X. Exit.
:~Enter option ~:Z
Invalid options. Please try again
Please choose one of the options below:
A. DNA Sequence Alignment
C. DNA Sequence Compression
H. Display the menu of options.
X. Exit.
:~Enter option ~:C
:~Enter DNA sequence ~:aaaZBbXcT
Invalid characters in the DNA sequence
:~Enter DNA sequence ~:ACGTACGTACGTACGTACGT
Original DNA Sequence:
ACGTACGTACGTACGTACGT
Compressed DNA Sequence:
ACGT(0,4)(0,8)(0,4)
:~Enter option ~:x
Exiting program...
Beware of computational biologist they screw genes and protein!
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
