Journal article
Space-conserving optimal DNA-protein alignment
Proceedings / IEEE Computational Systems Bioinformatics Conference, pp.80-88
2004
Handle:
https://hdl.handle.net/2376/114358
PMID: 16448002
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.
Metrics
9 Record Views
Details
- Title
- Space-conserving optimal DNA-protein alignment
- Creators
- Pang Ko - Department of Electrical and Computer Engineering, Iowa State University, USA. kopang@iastate.eduMahesh NarayananAnantharaman KalyanaramanSrinivas Aluru
- Publication Details
- Proceedings / IEEE Computational Systems Bioinformatics Conference, pp.80-88
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Publisher
- United States
- Identifiers
- 99900547597701842
- Language
- English
- Resource Type
- Journal article