align

Documentation

Overview

Package align provides functionality for aligning sequences.

Alignment Steps

Alignments are represented as Steps. Each step when aligning two sequences can be either taking a character from each sequence and aligning them together, or taking only one character and aligning it with a gap. The match step covers the case of a mismatch as well.

For example, the alignment of "blablab" and "blrblbr":

blablab-
|| || |
blrbl-br

Can be represented in steps as:

[match, match, match, match, match, deletion, match, insertion]

Index

• Constants
• type Step
  • func Global(a, b []byte, m SubstitutionMatrix) (steps []Step, score float64)
  • func Local(a, b []byte, m SubstitutionMatrix) (steps []Step, ai, bi int, score float64)
  • func (s Step) String() string
• type SubstitutionMatrix
  • func (m SubstitutionMatrix) Get(a, b byte) float64
  • func (m SubstitutionMatrix) GoString() string
  • func (m SubstitutionMatrix) Symmetrical() SubstitutionMatrix

Constants

const Gap = 255

Gap is the byte value for a gap in a substitution matrix.

Types

type Step

type Step byte

A Step is an alignment of one character from each sequence.

const (
	Match     Step = 1 // A character of A is aligned with a character of B.
	Deletion  Step = 2 // A character of A is aligned with a gap.
	Insertion Step = 3 // A character of B is aligned with a gap.
)

Possible values of a step.

func Global

func Global(a, b []byte, m SubstitutionMatrix) (steps []Step, score float64)

Global performs global alignment on a and b and finds the highest scoring alignment. Returns the steps relating to a, and the alignment score. Time and space complexities are O(len(a)*len(b)).

Uses the Needleman-Wunsch algorithm.

func Local

func Local(a, b []byte, m SubstitutionMatrix) (
	steps []Step, ai, bi int, score float64)

Local performs local alignment on a and b and finds the highest scoring alignment. Returns the steps relating to a, ai and bi as the start positions of the local alignment in a and b respectively, and the alignment score. Time and space complexities are O(len(a)*len(b)).

Uses the Smith-Waterman algorithm.

func (Step) String

func (s Step) String() string

String returns the name of the step.

type SubstitutionMatrix

type SubstitutionMatrix map[[2]byte]float64

A SubstitutionMatrix is a map from character pair p to the score of aligning p[0] with p[1]. Character 255 is reserved for gap. The pair [Gap,Gap] represents the general cost of opening a gap (gap-open). A matrix may be asymmetrical.

var (
	Levenshtein SubstitutionMatrix // Returns negated edit distance.
	PAM120      SubstitutionMatrix
	PAM160      SubstitutionMatrix
	PAM250      SubstitutionMatrix
	BLOSUM80    SubstitutionMatrix
	BLOSUM62    SubstitutionMatrix
	BLOSUM45    SubstitutionMatrix
)

func (SubstitutionMatrix) Get

func (m SubstitutionMatrix) Get(a, b byte) float64

Get returns the value of aligning a with b. Either argument may have the value Gap. Panics if the pair [a,b] is not in the matrix.

func (SubstitutionMatrix) GoString

func (m SubstitutionMatrix) GoString() string

GoString implements the fmt.GoStringer interface.

func (SubstitutionMatrix) Symmetrical

func (m SubstitutionMatrix) Symmetrical() SubstitutionMatrix

Symmetrical returns a copy of m. The copy also contains each pair flipped, mapped to the pair's original value.