Contextual alignment of biological sequences (Extended abstract).
We present a model of contextual alignment of biological sequences. It is an extension of the classical alignment, in which we assume that the cost of a substitution depends on the surrounding symbols. In this model the cost of transforming one sequence into another depends on the order of editing operations. We present efficient algorithms for calculating this cost, as well as reconstructing (the representation of) all the orders of operations which yield this optimal cost. A precise characterization of the families of linear orders which can emerge this way is given.
Gambin
Anna
A
Institute of Informatics, Warsaw University, Poland.
Lasota
Sławomir
S
Szklarczyk
Radosław
R
Tiuryn
Jerzy
J
Tyszkiewicz
Jerzy
J
D000465:Algorithms; D017124:Conserved Sequence; D010363:Pattern Recognition, Automated / Q000379:methods; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology