A Comprehensive Analysis of Bacterial Genomic Data
Advisor: Ms. Pochiraju
Internship Location: Intelliscience Training Institute
Onsite Mentor: Dr. Sohail Zaidi, San Jose State University Department of Engineering
Around 48 million people fall sick from foodborne illnesses each year within America, most stemming from the presence of bacteria such as E. Coli. However, due to increases in the use of antibiotics and small molecule medication, bacteria have begun mutating at more rapid rates, causing a change in symptoms seen within patients. Therefore, to understand how to better target and prevent foodborne illnesses from becoming rampant within communities, it’s necessary to analyze the location of these mutations and its impact on symptoms within patients.
My research will focus on analyzing the changes within E. Coli strains to determine where changes from the original E. Coli genetic DNA. I will create an algorithm using Python to run this analysis by using the national databases of genetic code, National Institute of Health and EcoCyc. The final product of this algorithm should demonstrate where the changes in the genetic code are through bar graphs, line charts, and base pair comparison charts. This algorithm will then hopefully be used for further analysis of other food bacterial strains including Salmonella and Listeria.
Project Blog
Week 0: Introduction to My Blog
Hi everyone! I’m Sonya, and welcome to my blog post, where I will dive deep into the intricate relationship between computer algorithms, genetic data, and foodborne illnesses. This week, I will focus on why understanding and identifying bacterial species quickly and effectively is necessary and how computer algorithms can help streamline this process.
Background:
48 million individuals fall sick from foodborne illnesses every year in the United States, and this statistic only increases as we consider countries across the globe. The presence of bacteria and fungi within our food is a constant issue that farmers struggle to manage and people suffer from; with every bacteria contained, mutated versions are developed to adapt to the changing environment. Therefore, researchers began looking into the applications of genome sequencing to better track these fast-growing changes within bacterial strains.
Whole genome sequencing (WGS) is a comprehensive method to analyze the complete sequence of DNA of different organisms including bacterial organisms, and it has been used in the past to track disease outbreaks like in the 2011 E. Coli O104:H4 outbreak in Europe. Prior research has been done within the field of WGS of bacterial strains, and this has been used within two main fields: healthcare and agriculture. Building strain identification databases has also been a previous focus for many researchers, and one prime example of this was the creation of the NCBI Pathogen Detection Database. It integrated bacterial and fungal pathogen genomic sequences whose sources include food, water, and other contaminated sources. This helped to predict the presence of different pathogens as well as identify their potential traits.
As a biological researcher, I have worked with gene editing in the past using the silencing of certain genes within a bacterial strain, and this includes working with bacterial cells of the E. Coli family. This sparked my interest in better understanding how mutations form within bacterial species, and it inspired my passion to create a computer algorithm to better identify these mutations.
Applications of Computer Algorithms:
For my research project, I want to utilize the established computer algorithms of global alignment to compare the bacterial strain, globally considered the base sequence, with mutated versions. This will provide a base for me to develop an algorithm that identifies the presence and location of mutations, which can be used by researcher more effectively prevent the spread of the bacterial strain within crops.
Project Proposal: https://docs.google.com/document/d/1zR22EYsy9k3DMCtXGuB3C8VasVDbNm-JzTwQWVE9nKc/edit?usp=sharing
On-site Internship Website: https://insinstitute.com/
Week 1: What is Gene Sequencing?
Hi everyone, welcome back to my blog! This week, I will be focusing on what gene sequencing is and how the data can be further analyzed in public health scenarios.
What is Gene Sequencing?
Gene sequencing determines the precise order of the nucleotides – adenine, thymine, cytosine, and guanine – of a DNA molecule found within an organism’s cell. First, the DNA molecules are extracted from liquid or solid samples of tissues before the fragmentation process takes place and adapters are attached to help with sequencing. Depending on the type of technology used within the gene sequencer, millions of short reads or multiple long reads of these nucleotide base pairs are carried out. Afterward, these short or long reads are aligned to a reference genome (which, in some cases, can be E. Coli for bacteria reads or GRCh38 for human reads). Now, the sequence is fully constructed and ready for any computational or manual analysis.
Gene sequencing retains importance throughout medical fields such as oncology, research spheres such as microbiology and evolutionary biology, and agriculture. It betters the scientific understanding of genetic diseases, targeted therapies, and evolutionary relationships among organisms.
Public Health Scenarios: Applications of Gene Sequencing
In my first blog post, I mentioned one specific instance of gene sequencing being used to help contain agricultural and medical outbreaks of foodborne illnesses. The 2011 E. Coli O104:H4 outbreak took place in Northern Germany and was caused by mutations within an enteroaggregative E. Coli (EAEC) strain that produced Shiga toxins. Whole genome sequencing (WGS) was utilized to identify the presence of mutations causing unusually virulent characteristics and antibiotic resistance and tracing its origins to Central Africa; however, it also highlighted how targeted diagnostics tests can be created to contain the spread of the disease more effectively.
This is not the only historical example of gene sequencing being used to help contain the spread of E. Coli, but this next instance had to do with the 2018 E. coli O157:H7 outbreak within romaine lettuce in the United States. The CDC utilized WGS to analyze the bacteria found within infected patients to determine that the outbreak had been caused by the Shiga toxin-producing E. coli (STEC) O157:H7. Through a comparison to genetic sequences from various sources across the country, the origin of the outbreak was traced back to Arizona. This situation demonstrated how gene sequencing is necessary and incredibly helpful for containing the spread of the disease, identifying the source, and determining the cause.
However, these public health scenarios also highlight an emergent need for computer algorithms to help streamline the comparison process of bacterial gene sequences. This will help ensure that mutations can be identified at a quicker pace and also allow for a more established understanding of the impact that mutations may have on patients, animals, and plants. Therefore, the literature review covered in this blog post emphasizes the need for a computer algorithm to compare gene sequences for medical, research, and agricultural applications.
Links for Further Research:
Week 2: Computer Algorithms for Bioinformatics and Genetics
Hi everyone, welcome back to my blog! This week, I will be focusing on the basics behind the computer algorithms created for the bioinformatics and genetics field while further expanding on the potential algorithms that I will use for my senior project.
Traditional Algorithm or Machine Learning?
The buzz words, “machine learning” and “artificial intelligence,” have integrated themselves into our every conversation of computer algorithms, but is it necessary to analyze gene sequencing? Gene sequences are currently stored in the NIH database in a text-based format with unique information such as accession number, locus, definition, source, organism, a features table, and the actual nucleotide sequence. While this data is being properly cleaned, then the type of algorithm has to be determined.
In the past, multiple different types of algorithms were used to perform comparisons between gene sequences. The first algorithm ever created for this purpose was the Needleman-Wunsch algorithm in 1970, which was used to carry out a global sequence alignment of two nucleotide sequences. It systematically compares every possible alignment by filling a scoring matrix based on substitution scores and gap penalties, ensuring the highest-scoring alignment is found. The algorithm follows three main steps: matrix initialization, scoring, and traceback to determine the optimal alignment. It is particularly useful for comparing sequences of similar length, such as homologous genes from different species, where global similarity is essential. However, the time complexity of the algorithm made it computationally expensive, so other algorithms were analyzed.
The Basic Local Alignment Search Tool, or BLAST, was created in 1990 to better the speed of these algorithms by approximating rather than computing any optimal alignments. It is a more widely used algorithm for comparing nucleotide sequences due to its computational efficiency. Lastly, algorithms were also created to compare multiple sequences (3+) at once including Clustal Omega and MUSCLE.
Conclusion
What can be understood from diving deeper into previously created algorithms is that the concept of comparing gene sequences has been successfully attempted before. However, what seems to be shared is that the concept of machine learning is not as heavily used within this sector of bioinformatics as researchers tended to rely more on deterministic, rule-based approaches instead. Therefore, for my algorithm, I have also concluded that machine learning does not hold as great of an impact or use within the comparison of sequences, so I will choose to create a traditional computer algorithm instead.
Week 3: Identifying E. coli Strains
Hi everyone, welcome back to my blog! This week, I will be identifying and analyzing the specific strains of E. Coli that I will be including in my dataset for my computer algorithms while further expanding on the biological importance behind each.
Data Point Zero: Non-mutated E. coli Strain
The purpose of this computer algorithm is to determine the presence of mutations within strains; therefore, the control, or base, strain should contain no mutations. There are records of many wild-type E. coli strains, but it’s important to select the correct one. E. coli K-12 is widely used in laboratories as its substrains, MG1655 and W3110, are well-characterized and free of major mutations. Overall, Scientists prefer E. coli K-12 due to its genetic stability, ease of manipulation, and lack of harmful virulence factors. However, E. coli NCM3722 is a wild-type derivative of the E. coli K-12 strain, closely related to MG1655 but with traits more representative of natural E. coli isolates. Researchers often use NCM3722 because it exhibits traits more representative of wild-type E. coli strains, so it offers a reliable baseline for studying bacterial physiology under various environmental conditions. Therefore, for this computer algorithm, E. coli NCM3722 will be utilized as the base sequence.
Additional Data Points for Training
To train this computer algorithm, it’s important to use mutated strains that have been implicated in previous public health crises due to their virulence, antibiotic resistance, or toxin production. E. coli O157:H7, a Shiga toxin-producing strain, caused severe foodborne outbreaks leading to hemolytic uremic syndrome and kidney failure. Similarly, E. coli O104:H4 was responsible for the 2011 outbreak in Germany, acquiring Shiga toxin genes and antibiotic resistance through horizontal gene transfer. Another concerning strain, E. coli ST131, is a multidrug-resistant pathogen linked to urinary tract and bloodstream infections, with mutations conferring resistance to extended-spectrum β-lactamases (ESBLs). These three strains are what I will use when I begin building my computer algorithm, and they will be compared to the original base strain for mutation identification practice.
Week 4: Data Cleaning
Hi everyone, welcome back to my blog! In the last blog post, we left off after identifying the specific strains of E. coli that would be included in my initial data set. This week, I began the data cleaning process with my potential E. coli strains. But, what exactly is data cleaning?
Introduction to Data Cleaning
Data cleaning is the process of identifying and correcting or removing errors, inconsistencies, and inaccuracies in a dataset. This helps to ensure that there is no bias in the data as well as improve the potential accuracy of the dataset being analyzed. Data cleaning is especially important when considering gene sequencing analysis, like this project is attempting to accomplish.
When sequencing the genome of bacteria (or any organism), inaccuracies and contamination can always take place, impacting portions of the read. For instance, there could be poor quality reads or the inclusion of artificial sequences, or adapters, that are included for library prep. These inaccuracies can potentially impact the results of future gene sequencing analysis, so data cleaning must be implemented during this project.
Data Cleaning Processes
To begin this process, I initially want to start analyzing the changes made within the coding sequence, as this will most directly impact protein creation. There are two data cleaning processes that I have chosen to implement as they are the most critical to increasing the accuracy of the project’s results. The first is to remove low-quality reads from the data subset, which includes using either cutadapt or Trimmomatic. These are two libraries within Biopython that can be easily utilized on Deepnote, the notebook I am using.
The second is to identify and remove duplicates in the strands that could potentially impact mutation identification. Since I am using well-known E. coli strains as the initial datasets for algorithm development, data cleaning is not as important. However, I want this algorithm to be applicable to multiple different forms of genomic data, which may contain inaccuracies. Therefore, this step is still important to implement. The next blog will demonstrate how I finished the data cleaning process, the results, and data pre-processing. Until next time!
Week 5: Data Preprocessing
Hi everyone, welcome back to my blog! Last blog, I talked a little bit about the data cleaning process, and I was able to implement it on two of the E. coli strains chosen: E. coli NCM3722 and E. coli O104:H4 (strand 2011C-3493). This blog post will cover how I specifically implemented both the data cleaning and data pre-processing to ensure higher accuracy.
Data Cleaning Overview
As mentioned in the last blog, data cleaning is not very necessary for well-known E. coli strains such as NCM3722, but what was discovered when the datasets were downloaded from NCBI was an inclusion of annotations. These annotations noted what proteins, if known, were created per genetic sequence, but their presence, though extremely important for analyzing the impact of mutations, was not necessary for initial algorithm development. Therefore, these annotations were removed, and raw nucleotide sequences were assembled into separate FASTA files.
What is Data Preprocessing?
The purpose of data preprocessing is to transform raw data into a clean, organized, and usable format for analysis. There are multiple types of data preprocessing that can be implemented, but the two that I have chosen for this project are alignment and sorting/indexing the file.
Alignment essentially aligns the experimental genome, which is E. coli O104:H4, to the reference E. coli strain for better mutation identification. The second preprocessing technique to be used is sorting and indexing the file, and its purpose is to arrange the aligned reads based on the position in the reference genome; the index file points to those positions within the file.
Results
The results of the first form of data preprocessing can be seen in the image below. The target sequence is that of NCM3722, while the query sequence is O104:H4; it can be seen that there are many dashes in between the sequences, which demonstrates gaps in alignment. This can mean there are insertions or deletions within the E. coli sequence.
The second form of data preprocessing was sorting and indexing the sequences. By defining functions whose purpose was to sort and index, portions of the sequence were separated based on their locus and the proteins they contributed to. The picture below shows a genetic code present in the reference genome but not in the experimental genome, referenced by their indexes.
That’s all for this blog post! Next blog, we will focus on algorithm development – see you soon!
Week 6: Algorithm Development
Hi everyone, welcome back to my blog! Last blog, I walked you all through both the data cleaning and data preprocessing process that I implemented to improve the dataset. This blog post will divert our attention away from coding back to the drawing board. Now that our dataset is ready, we need to create our algorithm.
Let’s reiterate the purpose of this project. We want to take one E. coli strain and identify the presence of mutations within it through comparison with a reference genome. Our data set has already been aligned, sorted, and indexed, meaning that it is ready for the comparison. But how exactly do we derive an algorithm that will identify the presence of mutations and what type of mutation it is?
This simple flowchart walks us through the thought process behind my initial algorithm. First, checking if bases are equal helps identify whether there is a discrepancy in bases and, therefore, highlights the presence of mutations. Then, the algorithm begins iterating through each aligned position and checks if the bases match. If they do, the loop continues without recording any change. Each step afterwards demonstrates specificity behind mutations that are important to identify. If there is a dash present within the target genome, then it is due to the presence of an insertion or deletion; if not, then a substitution has been made. After all positions are analyzed, the mutations are compiled into a final report, which is printed at the end.
The initial computer program will highlight the presence of mutations, the number of mutations, and the sequence ID of these mutations. After this first step, the algorithm will later become more complex to better identify the types of mutations and their impact on specific protein development. That’s all for this blog post, until next time!
Week 7: Initial Algorithm Setback
Hi everyone, welcome back to my blog! In the last blog post, I described the flowchart behind the basic algorithm I would like to implement initially. This blog post will highlight the work on this basic algorithm I have completed this week.
What needed to first be created was a loop algorithm that could iterate through both the target sequence and the query sequence and identify the presence of mutations. The first problem that I encountered was the fact that for every locus, the loop was identifying the presence of mutations. I decided that this could be due to sequence length mismatches or misaligned sequences. However, it was later determined that the reason why this problem was taking place was due to a very obvious issue.
The method by which each sequence was referenced for comparison was through the sequence ID, and this sequence ID was how each sequence was sorted and indexed as well. Therefore, to reference each index, you utilize the sequence ID. However, for NCM3722 (the base E. coli strand), the sequence ID looked like “lcl|CP011495.1_cds_AKO54450.1_1” while the sequence ID for O104:H4 looked like “lcl|NC_018658.1_cds_WP_000059111.1_1”. Different letter and number indexes would confuse the algorithm during alignment and iteration, so each index was being labeled as a mutation.
This, therefore, highlighted two potential issues that need to be resolved. First, are O104:H4’s and NCM3722’s coding sequences, after cleaning and preprocessing, compatible for comparison? Or is there more editing and research necessary before they can be compared for mutations? Additionally, if they are not compatible, then it’s important to either identify a strain that can be compared with NCM3722’s coding sequence or understand what other computational methods need to be used to better facilitate this comparison.
This is a major setback within the coding and analysis process of these gene sequences, but all it means is that we go back to the drawing board. Next week, I will cover the findings from my research into these points and, hopefully, demonstrate some changes within the algorithm’s outlook. Until next time!
Week 8: BLAST Algorithm
Hi everyone, welcome back to my blog! In the last blog post, I delved into a little bit of the problems that I was facing due to the dataset cleaning process and how that impacted the results that I was receiving. The first order of business was determining compatibility.
Because the O104:H4 strain that I had downloaded from NCBI was a pathogenic strain while NCM3722’s strain was from a lab, there was a higher chance of inversion, insertions, and deletions. Therefore, I had to find another lab strain that I could use to compare to NCM3722 for better algorithmic accuracies. I decided to start even simpler with K-12 MG1655, which is the most common reference lab strain and is used widely in research. K-12 MG1655 and NCM3722 are evolutionarily similar in that NCM3722 is descended from K-12 MG1655, so there will not be a significant presence of insertions and deletions within the strain.
This week, I aimed for a different approach. Before, I was trying to utilize simple sorting and indexing to compare for mutations in one of the genomic strains. However, when these E. coli strains are sequenced, they are given locus tags that differ from strain to strain, even if they refer to orthologous, or equivalent, genes. I decided to do some more research on methods that are used to compare genomic strains, and I landed on the BLAST algorithm, which I mentioned in my introductory blogs.
The purpose of the BLAST algorithm is to find regions of similarity between biological sequences, and I hope to utilize it to iterate through these genomic sequences to find areas of similarity and mutations. The following screenshot highlights the tabular form of the results that the BLAST comparison derived.
Query_id and subject_id both highlight the tags given to each protein-coding sequence within the genome sequences. It can be seen why the previous algorithm could not identify mutations, as each sequence ID has a different name. The %identity highlights the percentage of matching sequences, while alignment_length demonstrates the number of aligned nucleotide bases. This highlights the presence of exact coding sequences, which shows a progression from the previous algorithm.
For the next blog, I will continue working on utilizing the BLAST algorithm and finalize the mutation detection. Until next time!
Week 9: Data Collection
Hi everyone, welcome back to another blog! In the last blog post, I demonstrated the different method failures I experienced when creating my algorithm before I was able to identify a specific method, the BLAST algorithm, that was successful.
This week, much of my efforts were focused on ensuring that this BLAST algorithm was working to the highest capacity and efficiency. To understand what I edited and fixed, we have to start all the way at the beginning: data cleaning. When you are analyzing gene sequencing in the form of a .txt file and, later, a fasta file, then what you come across are certain descriptors for each portion of the sequence. There are two main sections we need to be concerned with: ID and description. The local ID uniquely labels a sequence within a given dataset or system, but not necessarily globally. The description, however, contains a locus tag, which is systematically applied to every gene in a genome. Since the default of the BLAST algorithm is to use the local ID, the data had to be edited to ensure that the locus tag was utilized instead, so that the impact on the E. coli proteins could be identified more effectively.
After this data cleaning was completed, the percentage of genes that contained mutations was first identified. This screenshot, seen below, highlights what the algorithm is now currently outputting.
Afterwards, I iterated through the locus tags with mutations to identify a list of mutated proteins while also ensuring there was no repetition. The output can be seen in the screenshot below as well.
I, then, was able to separate these protein mutations within five specific categories: Genetic Pathways, Signaling/Cell Division/Cell Stability, Metabolism, Other, and Unknown; the genetic pathways section was then split into: Regulatory/Alteration, Duplication, and Transcription/Translation. I was able to highlight the highest impacted areas of cellular activity, which I hope to replicate with three other strains before the end of this project using this algorithm.
Within the next week, I hope to automate this process of categorizing proteins while also iterating through different strains and demonstrating the outputs within graphs. Until next time!
Week 10: Data Collection
Hi everyone, welcome back to my blog! In the last post, the use of BLAST within my algorithm development was discussed. In this blog post, I will cover the different pieces of data that I acquired from my project.
The first was pairwise alignment using the PairwiseAligner(). Essentially, the highest score for each alignment was measured, and then it was ordered with the highest score at the beginning and the lowest score towards the end. I was able to replicate it for all three strains that are being analyzed: E. coli K-12 MG1655, E. coli O157:H7, and E. coli O119:H4. The second was analyzing the BLAST algorithm’s outputted alignment lengths. Both a query-alignment-length plot, which shows how much of each query aligns to targets, and a plot with the total sequence length aligned for each locus tag were generated for each strain being analyzed.
The last round of data collection was for identifying types of mutations. There are two specific mutations that this algorithm will target: frameshift mutations and point mutations. Frameshift mutations include insertions, which add nucleotides from gene sequences, and deletions, which subtract nucleotides from gene sequences. Point mutations include silent, which do not impact protein translation; missense, which do impact protein translation; and nonsense, which initiate premature stop codons. This data was visualized in bar graphs that show the categorization of these proteins within each E. coli strain.
These graphs were included during my final project report and will be further analyzed within this research paper. This paper will be available during my Senior Project Presentation later this month. Until next time!
Week 11: Final Presentations
Hi everyone, and welcome back to my last blog post! Time has flown by so quickly throughout this entire senior project process, and I am really grateful for the experiences that I have had. I had the opportunity to be certified in using the Illumina iSeq 100 while also learning more about the gene sequencing process. I even broadened my skills in bioinformatics and algorithm development with all the necessary back-and-forth within this process. Now, I am gearing up for our final presentation this Saturday, where I have the opportunity to present the work that I have done to my peers and other audience members. It’s been a journey that I will truly appreciate as it has helped me better both my research and my communication skills, and I hope you all had fun with me. Thank you for sticking around!