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

• Variables
• func MinWordsPerFilterHit(hitLength, wordLength, maxErrors int) int
• type Filter
  • func New(index *kmerindex.Index, params *Params) (f *Filter)
  • func (self *Filter) Filter(query *seq.Seq, selfAlign, complement bool, morass *morass.Morass) (err error)
• type FilterHit
  • func (self FilterHit) Less(y interface{}) bool
• type Merger
  • func NewMerger(index *kmerindex.Index, query *seq.Seq, filterParams *Params, selfCompare bool) (m *Merger)
  • func (self *Merger) FinaliseMerge() (trapezoids Trapezoids)
  • func (self *Merger) MergeFilterHit(hit *FilterHit)
• type Params
• type Trapezoid
• type Trapezoids
  • func (self Trapezoids) Len() int
  • func (self Trapezoids) Less(i, j int) bool
  • func (self Trapezoids) Sum() (a, b int)
  • func (self Trapezoids) Swap(i, j int)
• type TubeState

Variables

var (
	MaxIGap    int     = 5
	DiffCost   int     = 3
	SameCost   int     = 1
	MatchCost  int     = DiffCost + SameCost
	BlockCost  int     = DiffCost * MaxIGap
	RMatchCost float64 = float64(DiffCost) + 1
)

Default global parameters

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(index *kmerindex.Index, params *Params) (f *Filter)

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

func (*Filter) Filter

func (self *Filter) Filter(query *seq.Seq, selfAlign, complement bool, morass *morass.Morass) (err 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 seaching - behavior is undefined if the the sequences are not the same. A morass is used to store and sort individual filter hits.

type FilterHit

type FilterHit struct {
	QFrom     int
	QTo       int
	DiagIndex int
}

Type to store individual q-gram filter hits.

func (FilterHit) Less

func (self FilterHit) 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 FilterHits because of differences in the underlying sort algorithms and their respective sort stability. This appears to have some impact on FilterHit 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(index *kmerindex.Index, query *seq.Seq, filterParams *Params, selfCompare bool) (m *Merger)

Create a new Merger using the provided kmerindex, query sequence and filter parameters. If selfCompare is true only the upper diagonal of the comparison matrix is checked to save time.

func (*Merger) FinaliseMerge

func (self *Merger) FinaliseMerge() (trapezoids Trapezoids)

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

func (*Merger) MergeFilterHit

func (self *Merger) MergeFilterHit(hit *FilterHit)

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 {
	Next        *Trapezoid // Organized in a list linked on this field
	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

Trapezoid slice type used for sorting Trapezoids during merge.

func (Trapezoids) Len

func (self Trapezoids) Len() int

Required for sort.Interface

func (Trapezoids) Less

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

Required for sort.Interface

func (Trapezoids) Sum

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

Return the sum of all Trapezoids in the slice.

func (Trapezoids) Swap

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

Required for sort.Interface

type TubeState

type TubeState struct {
	QLo   int
	QHi   int
	Count int
}

A TubeState stores active filter bin states.