SWAMP Align - Shannon Steinfadt

Sequence Alignment

In bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences. - Wikipedia

Sequence alignment looks at the underlying structure of sequences of DNA and RNA, the strings of "G" "A" "T" "G" (and "U"s instead of "T"s in RNA).

By looking for similar not necessarily the exact same underlying structure, sequence alignment is seeking similar underlying chemical structure, which in theory will fold the same way and produce the same or similar three-dimensional structures and produce similar functionality.

The work discussed here uses the Smith-Waterman (SWA) sequence alignment algorithm. The SWA uses a dynamic programming approach to find the highest scoring possible alignment, unlike other alignment algorithms that use a heuristic (approximation) approach. One of the difficulties is the intense number of computations and the high memory costs of the algorithm. That is where the parallelism methods discussed here (and in the paper/poster links) are vital to creating usable solutions.

 

Updates

October 2013

For those of you attending the Grace Hopper Celebration of Women in Computing in Minneapolis, MN, there will be a poster session on the sequence alignment work called "Beyond the Data SWAMP: Parallel Paradigms for Large Scale Sequence Alignment." In addition, Shannon will be giving a talk entitled "Gaming the System: Gamification for Nuclear and High-Hazard Response Training"

September 2013

Journal paper published and available online “Fine-Grained Parallel Implementations for SWAMP+ Smith-Waterman Alignment,” Shannon Irene Steinfadt. J. of Parallel Computing. Available online 4 September 2013, ISSN 0167-8191, http://dx.doi.org/10.1016/j.parco.2013.08.008.

March 2012

Filed United States Patent Application 13/423,085: “Computer-Facilitated Parallel Information Alignment and Analysis.” This patent outlines approaches for an extended Smith-Waterman genomic data sequence alignment algorithm used for finding similarities in data strings that can discover multiple sub-string alignments efficiently on parallel computing architectures.

March 2010

Shannon defended the Ph.D. dissertation Smith-Waterman Sequence Alignment for Massively Parallel High-Performance Computing Architectures.

November 2009

If you are attending Supercomputing SC'09 conference, stop by to visit Shannon at the ACM Student Research Poster Competition. The poster is titled Large-Scale Wavefront Parallelization on Multiple Cores for Sequence Alignment. She is the recipient of the Broader Engagement Grant for SC for the second year.

September 2009

Invited speaker for the CRA-W Workshop at Grace Hopper Celebration of Women in Computing - The Road to Graduate School

Shannon started a Graduate Research Assistantship at Los Alamos National Lab with the Decision and Risk Anaylsis, continuing her research with parallel and HPC Smith-Waterman sequence alignment.

June 2009

Shannon held a summer position at Los Alamos National Laboratory with the Performance and Architectures Lab.  She spent the summer looking at performance metric and parallel algorithms on several architectures, including SSE intrinsics and JumboMem.

Shannon Steinfadt and Kevin Schaffer had a paper that appeared in the 4th Ohio Collaborative Conference for Bioinformatics (OCCBIO), Cleveland, Ohio, June 15-17, 2009 “Parallel Approaches for SWAMP Sequence Alignment.”

 

Links