GRAPH-BASED DYNAMIC PROGRAMMING ALGORITHM FOR de novo PROTEIN STRUCTURE
MODELING USING CRYO-EM VOLUME MAPS


Kamal Al Nasr
PhD Candidate & Research Scholar
Department of Computer Science
Old Dominion University

ABSTRACT

Proteins are the molecules carry out vital functions in every cell. Protein in
nature folds into a unique and energetically favorable 3-dimensional structure
which is critical and unique to its biological function. The current
experimental methods of protein structure determination are not suitable for
all kind of proteins. Electron Cryo-microscopy (CryoEM) is an attractive
technique in protein structure determination, particularly for the proteins
that are challenging for X-ray and NMR techniques.

The volumetric maps at medium resolution (~6 to 10) generated by CryoEM
technique proposed a new challenge for structure determination. At the medium
resolution, some features of the protein can be visually and computationally
identified such as the location and orientation of secondary structures
elements (SSEs). However, the order and direction of the SSEs detected from the
CryoEM volume map is not visible. In order to determine the protein structure,
the topology of the SSEs has to be figured out and then the backbone can be
built.

In this talk, I will present an approach to translate the SSE topology problem
into a graph problem. I will present a dynamic programming method, 'TopoDP', to
derive the constrained shortest path and the constrained k shortest paths
algorithm to derive the top ranked topologies. This approach shows the improved
accuracy, speed and memory use when compared with existing methods. TopoDP
provides a fast geometrical method of ranking the topologies without the
construction of the protein chain that is often time consuming.



VITA

Kamal H. Al Nasr was born in Irbid city, Jordan. He attended Yarmouk
University, Irbid in 1999, receiving his bachelor degree of science in Computer
Science on February 2003. In his Bachelor study, he was listed on the honor
list of the college of science. He entered the graduate school in the
Department of Computer Information Systems at Yarmouk University, Irbid in
2003, receiving a Master's of Computer Information Systems in August, 2005. He
ranked the 2nd out of the students who graduated in the same academic year.
While attending the graduate school at Yarmouk University, he served as a
Math/Computer teacher in United Nations schools. He moved to United stated in
2007, entering the graduate school in the Department of Computer Science at New
Mexico State University, New Mexico. He Obtained a Master's of Science in
Computer Science in 2011. During his stay at NMSU, he worked at the Center for
Research Excellence in Bioinformatics and Computational Biology ( CREST). He
was awarded a graduate assistantship excellence award for his research
contribution and outstanding. He joined the graduate school in the Department
of Computer Science at Old Dominion University, Virginia, in the Ph.D. program
in September, 2009. He awarded College of Science's university fellowship on
July 2010. While in Ph.D. program, he served as an instructor of one of
undergraduate courses. Mr. Al Nasr has multiple publications in many national
and international refereed journals and conferences such as BMC Bioinformatics,
Journal of Bioinformatics and Computational Biology, International Journal of
Bioinformatics and Data Mining, and IEEE BIBM conference.