Alignment for Biological Sequences

Wang, Tsai Cheng

Alignments provides a computational way to locate the regions of homology on two sequences. Given a score to each competing pair of acids, hills and valleys are therefore reflected in a 3-D alignment map where X- and Y-axis represent the elements of two given sequences, and Z-axis shows the scores. A bridge goes through these hills and valleys gives us a “benefit” in returned. To find an alignment is equivalent to build a bridge connecting those hills with an acceptable benefit in a diagonal fashion. A single bridge that covers all elements in both sequences forms a global alignment. A local alignment gives a bridge constructed within limited costs. Gap insertions allow a bridge inter-crossing diagonals with penalty.

The following presents the algorithms and executables of my works in these issues.

DNA

Align nucleic acids to nucleic acids locally.

Protein

Align amino acids to amino acids locally. It allows to open a single long gap which maximizes to user's request.

Group-Similarity Segment (GSS)

Group-Similarity Segment (GSS) represents the significant-score segment that reflects a group of local alignments concentrated on portions of a sequence. GSS shows many-on-one instead of one-on-one similarity comparisons.