[Pareto-optimal alignment of biological sequences].
The problem of alignment of two symbol sequences is considered. The validity of the available algorithms for constructing optimal alignment depends on the weighting coefficients which are frequently difficult to choose. A new approach to the problem is proposed, which is based on the use of vector weighting functions (instead of tradionally used scalar ones) and Pareto-optimal alignment (an alignment that is optimal at any choice of weighting coefficient will always be Pareto-optimal). An efficient algorithm for constructing all Pareto-optimal alignments of two sequences is proposed. An approach to choosing a "biologically correct" alignment among all Pareto-optimal alignments is suggested.
Roĭtberg
M A
MA
Institute of Mathematics Problems of Biology, Russian Academy of Sciences, Pushchino, Moscow Region, Russia.
Semionenkov
M N
MN
Tabolina
O Iu
OIu
D000465:Algorithms; D000595:Amino Acid Sequence; D000818:Animals; D001483:Base Sequence; D008969:Molecular Sequence Data; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment
D011506:Proteins