filter

Documentation

Overview

Package providing PALS sequence hit filter routines based on 'Efficient q-gram filters for finding all 𝛜-matches over a given length.'

Kim R. Rasmussen, Jens Stoye, and Eugene W. Myers. J. of Computational Biology 13:296–308 (2006).

Index

• func MinWordsPerFilterHit(hitLength, wordLength, maxErrors int) int
• type Filter
  • func New(ki *kmerindex.Index, params *Params) (f *Filter)
  • func (f *Filter) Filter(query *linear.Seq, selfAlign, complement bool, morass *morass.Morass) error
• type Hit
  • func (h Hit) Less(y interface{}) bool
• type Merger
  • func NewMerger(ki *kmerindex.Index, query *linear.Seq, filterParams *Params, maxIGap int, ...) *Merger
  • func (m *Merger) FinaliseMerge() Trapezoids
  • func (m *Merger) MergeFilterHit(h *Hit)
• type Params
• type Trapezoid
• type Trapezoids
  • func (tr Trapezoids) Len() int
  • func (tr Trapezoids) Less(i, j int) bool
  • func (tr Trapezoids) Sum() (a, b int)
  • func (tr Trapezoids) Swap(i, j int)

Functions

func MinWordsPerFilterHit

func MinWordsPerFilterHit(hitLength, wordLength, maxErrors int) int

Ukonnen's Lemma: U(n, q, 𝛜) := (n + 1) - q(⌊𝛜n⌋ + 1)

Types

type Filter

type Filter struct {
	// contains filtered or unexported fields
}

Filter implements a q-gram filter similar to that described in Rassmussen 2005. This implementation is a translation of the C++ code written by Edgar and Myers.

func New

func New(ki *kmerindex.Index, params *Params) (f *Filter)

Return a new Filter using ki as the target, and filter parameters in params.

func (*Filter) Filter

func (f *Filter) Filter(query *linear.Seq, selfAlign, complement bool, morass *morass.Morass) error

Filter a query sequence against the stored index. If query and the target are the same sequence, selfAlign can be used to avoid double searching - behavior is undefined if the the sequences are not the same. A morass is used to store and sort individual filter hits.

type Hit

type Hit struct {
	From     int
	To       int
	Diagonal int
}

Type to store individual q-gram query filter hits.

func (Hit) Less

func (h Hit) Less(y interface{}) bool

This is a direct translation of the qsort compar function used by PALS. However it results in a different sort order (with respect to the non-key fields) for Hits because of differences in the underlying sort algorithms and their respective sort stability. This appears to have some impact on Hit merging.

type Merger

type Merger struct {
	// contains filtered or unexported fields
}

A Merger aggregates and clips an ordered set of trapezoids.

func NewMerger

func NewMerger(ki *kmerindex.Index, query *linear.Seq, filterParams *Params, maxIGap int, selfCompare bool) *Merger

Create a new Merger using the provided kmerindex, query sequence, filter parameters and maximum inter-segment gap length. If selfCompare is true only the upper diagonal of the comparison matrix is examined.

func (*Merger) FinaliseMerge

func (m *Merger) FinaliseMerge() Trapezoids

Finalise the merged collection and return a sorted slice of Trapezoids.

func (*Merger) MergeFilterHit

func (m *Merger) MergeFilterHit(h *Hit)

Merge a filter hit into the collection.

type Params

type Params struct {
	WordSize   int
	MinMatch   int
	MaxError   int
	TubeOffset int
}

Type for passing filter parameters.

type Trapezoid

type Trapezoid struct {
	Top, Bottom int // B (query) coords of top and bottom of trapzoidal zone
	Left, Right int // Left and right diagonals of trapzoidal zone
}

Type to store a successfully filtered w × e Parallelogram

type Trapezoids

type Trapezoids []Trapezoid

Trapezoids implements the sort.Sort interface.

func (Trapezoids) Len

func (tr Trapezoids) Len() int

Required for sort.Interface

func (Trapezoids) Less

func (tr Trapezoids) Less(i, j int) bool

Required for sort.Interface

func (Trapezoids) Sum

func (tr Trapezoids) Sum() (a, b int)

Return the sum of all Trapezoids in the slice.

func (Trapezoids) Swap

func (tr Trapezoids) Swap(i, j int)

Required for sort.Interface