Open AccessComparison of Coding DNA
Author(s) -
Christian N. S. Pedersen,
Rune B. Lyngsø,
Jotun Hein
Publication year - 1998
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v5i3.19276
Subject(s) - coding (social sciences) , algorithm , conjecture , computer science , quadratic equation , dna , affine transformation , mathematics , dna sequencing , theoretical computer science , genetics , discrete mathematics , biology , statistics , geometry , pure mathematics
We discuss a model for the evolutionary distance between two coding DNA sequences which specializes to the DNA/protein model proposed in Hein [3]. We discuss the DNA/protein model in details and present a quadratic time algorithm that computes an optimal alignment of two coding DNA sequences in the model under the assumption of affine gap cost. The algorithm solves a conjecture in [3] and we believe that the constant factor of the running time is sufficiently small to make the algorithm feasible in practice.