title: Contextual alignment of biological sequences (Extended abstract).
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.
authors.affiliation: Institute of Informatics, Warsaw University, Poland.
authors.forename: Anna
authors.initials: A
authors.lastname: Gambin
authors.forename: Sławomir
authors.initials: S
authors.lastname: Lasota
authors.forename: Radosław
authors.initials: R
authors.lastname: Szklarczyk
authors.forename: Jerzy
authors.initials: J
authors.lastname: Tiuryn
authors.forename: Jerzy
authors.initials: J
authors.lastname: Tyszkiewicz
mesh_terms: D000465:Algorithms; D017124:Conserved Sequence; D010363:Pattern Recognition, Automated / Q000379:methods; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology