Example of sequence alignment in DNA Baser Sequence Aligner
Sequence alignment is a procedure which may be implicit or explicit conducted in biological study that compares two or more biological sequences (whether DNA, RNA, or protein). This procedure attempts to infer which positions within the sequence are homologous. Homologous refers to that sites those share the evolutionary history that are found to be common.
It is that alignment whose score lies in the neighborhood of the optimal score.
Between the pair of proteins or nucleic acids the optimal alignment does not necessarily reflect the correct biological evolution.
Alignments of those proteins are based on the DNA sequences based on the evolutionary changes. These alignments are different from the alignments that minimizes the edit distance
In many cases the edit distance alignment is a better approximation than the biological one.
Methods are presented for representing the alignments whose score is under any given delta from the original score.
The number of alignments is represented using a compact graph, which helps in imposing additional biological constraints and selects one desirable constraint for the large set.
The graphical representations show in a dramatic way, all the possible alignments without the need of enumerate them.
Multiple sequence alignment:
Multiple sequence alignment is a optimization problem that is computationally hard and which involves the considerations of different alignments in order to find an optimal one, when given a measure of goodness of alignments.
The multiple sequence alignment problems use various criteria of optimality that is basically shown in NP-HARD.
Dynamic programming algorithms are used for the search of optimal alignments. They are constrained to unwieldy space requirements by large number of sequences.
There are several methods devised that helps to reduce the search space for an optimal alignment under a sum of pair measure.
Dynamic programming is widely used to solve the optimization problem of aligning sequences.
The asymptotic complexity of dynamic programming increases exponentially with the dimension.