SOU Ashland's Ezra Fader with computational biology poster

SOU student explores computational biology through NSF program

SOU student Ezra Fader traveled to Montana State University in Bozeman, Montana, this summer to take part in a National Science Foundation-funded Research Experiences for Undergraduates (REU) program that focused on computation and algorithms.

The Computation and Algorithms REU accepted nine students out of roughly 60 to 70 applicants. Fader first heard about REUs through SOU advisor and associate professor Brandon Ashley and recent mathematics graduate Will Childs, then found the Montana State program through the National Science Foundation’s ETAP portal.

The application required a resume, personal statement and two letters of recommendation. Fader was accepted the day after applying.

“The day after submission, I was accepted and was told I had a day to accept the offer,” Fader said. “So all my plans for summer had essentially shifted in a single day.”

Fader spent the summer working on string-comparison algorithms, which are methods computers use to compare DNA sequences of information. This kind of work can be useful in computational biology, including genome comparison.

Most of the group’s research centered on a problem called Longest Common Subsequence on Two Directed Acyclic Pangenome Graphs. A pangenome graph is a way of representing genetic information from multiple genomes while showing both their similarities and differences. The team was trying to find an efficient way to compare two of these graphs and identify the longest subsequence they had shared.

SOU Ashland's Ezra Fader's computational biology workA big part of the problem was figuring out how the algorithm would behave as the amount of data increased. Computer scientists describe that by using Big O notation, which does not tell you exactly how many seconds a program will take to run. Instead, it shows how quickly the amount of work grows as the size of the problem gets larger. In this case, “n” represents the number of characters in the larger graph.

The team started with an O(n⁴) approach, meaning that for a problem of size n, the amount of work grows roughly with n raised to the fourth power. In simpler terms, if the size of the problem doubled, the amount of work could increase by about 16 times.

Fader and the rest of the team found an O(n³) approach instead. With that version, the amount of work grows roughly with n cubed, so doubling the size of the problem would increase the amount of work by about eight times.

The research was presented in a poster co-authored by Fader and a fellow undergraduate researcher Oskar Cole. Titled “Longest Common Subsequence of Two Acyclic Pangenome Graphs,” the poster explains the problem the group worked on, their algorithm, its O(n³) runtime, and possible directions for future research.

This difference is critical when the algorithm is working with large problems like DNA sequencing, where the problem size can extend beyond billions of characters.

The new approach used dynamic programming, a technique where an algorithm saves results from smaller parts of a problem and reuses them instead of calculating the same things repeatedly. The idea for that improvement came to Fader while hiking.

“I continuously tried to come up with counterexamples, but I was unable to prove myself wrong,” Fader said.

A counterexample is a case that shows an algorithm does not always work. Even if an idea works thousands or millions of times, one counterexample can be enough to show that there is still a problem with it.

After the hike, Fader implemented the idea and ran millions of tests without finding a failure. They then brought the idea to their research partner, who was initially unsure but became convinced after the two worked through it together.

The group then brought the idea to their advisor, who was more cautious. Fader said their advisor pointed out that researchers can sometimes test an algorithm for months without finding the one case that breaks it.

That meant the team had to do more than just test the algorithm. They also had to work through why it should be correct and support it mathematically.

Most days started around 9 a.m. in the REU student workspace. Fader spent time researching papers, working through algorithms on whiteboards, writing Python programs and running tests.

The whiteboard work was a large part of the process. Before implementing an idea, the team could draw out different cases, test possible solutions and think through how much work an algorithm would require.

The research group included two professors, two post-graduate students, a master’s student, a doctoral student and the two undergraduate students. The team met three afternoons each week, while all REU students also met twice a week to present progress on their projects.

Fader said the program involved a different kind of problem solving than used in regular coursework.

“I learned how to read research papers in pure computer science and construct proofs with logical statements more complex than what is normally seen in academic coursework,” Fader said.

Several SOU courses helped Fader prepare, especially Algorithms, Theory of Computation and previous mathematics classes. Those courses gave Fader experience building algorithms, thinking about computational limits and writing proofs to support their claims.

Outside of research, the students also spent time exploring Montana and Wyoming. They went on weekly hikes and took a camping trip to Yellowstone and Grand Teton National Parks.

Fader enjoyed the scenery and plant life, including the red clover seen throughout the area.

Being away from friends and family was one of the more challenging parts of the summer.

“I did have friends at the REU, but it’s not quite the same crowd that you get at SOU,” Fader said. “Y’all are irreplaceable.”

The program also made Fader think more seriously about graduate school. Fader considered graduate computer science more after the experience, but is currently leaning toward applied mathematics programs.

For students interested in applying to an REU, Fader recommends strengthening their resume, talking with professors regularly and putting time into their personal statement.

“Beef up your resume, reach out to professors for advice regularly, and don’t slack on your personal statements,” Fader said.

Story by Felicity Johnson, SOU Computer Science major