title: Space-conserving optimal DNA-protein alignment.
abstract: DNA-protein alignment algorithms can be used to discover coding sequences in a genomic sequence, if the corresponding protein derivatives are known. They can also be used to identify potential coding sequences of a newly sequenced genome, by using proteins from related species. Previously known algorithms either solve a simplified formulation, or sacrifice optimality to achieve practical implementation. In this paper, we present a comprehensive formulation of the DNA-protein alignment problem, and an algorithm to compute the optimal alignment in O(mn) time using only four tables of size (m + 1) x (n + 1), where m and n are the lengths of the DNA and protein sequences, respectively. We also developed a Protein and DNA Alignment program PanDA that implements the proposed solution. Experimental results indicate that our algorithm produces high quality alignments.
authors.affiliation: Department of Electrical and Computer Engineering, Iowa State University, USA. kopang@iastate.edu.
authors.forename: Pang
authors.initials: P
authors.lastname: Ko
authors.forename: Mahesh
authors.initials: M
authors.lastname: Narayanan
authors.forename: Anantharaman
authors.initials: A
authors.lastname: Kalyanaraman
authors.forename: Srinivas
authors.initials: S
authors.lastname: Aluru
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D004247:DNA / Q000235:genetics*; D044962:Data Compression / Q000379:methods; D008969:Molecular Sequence Data; D011506:Proteins / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*
chemical_list: D011506:Proteins; D004247:DNA