`Name:`

SeqMap `Domain:`

Bioinformatics `Functionality:`

Perform short sequence mapping by solving an approximate string matching problem `Input:`

a set of sequence reads T, a genome P and a maximum number of mismatches e `Output:`

The set of mappable reads $T_{m}$
An innovative approach for testing bioinformatics programs using metamorphic testing 10.1186/1471-2105-10-24

`Description:`

`Property:`

$m_{i’}$ should still be mappable to P. there should exist at least one common location for $m_{i}$ and $m_{i’}$ `Source input:`

T,P,e `Source output:`

$T_{m_{1}}$ `Follow-up input:`

T,P,e, a subset M($m_{1},m_{2},\dots,m_{i}$) of $T_{m_{1}}$, L as one of M’s mismatch numbers `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

Arbitrarily choose a L', such that $L <L' \leq e$, and introduce (L' - L) new mismatches on $m_{i}$ (denoted as $m_{i’}$ ). `Output relation:`

$m_{i’}$ should still be mappable to P. there should exist at least one common location for $m_{i}$ and $m_{i’}$ `Pattern:`

`Description:`

`Property:`

$m_{i’}$ should still be mappable to P. there should exist at least one common location for $m_{i} and $m_{i’ `Source input:`

T,P,e `Source output:`

$T_{m_{1}}$ `Follow-up input:`

T,P,e, a subset M($m_{1},m_{2},\dots,m_{i}$) of $T_{m_{1}}$, L as one of M’s mismatch numbers `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

Arbitrarily choose a L', such that $0 \leq L' \leq L$, and delete (L' - L) mismatches on $m_{i}$ (denoted as $m_{i’}$ ). `Output relation:`

$m_{i’}$ should still be mappable to P. there should exist at least one common location for $m_{i} and $m_{i’ `Pattern:`

`Description:`

`Property:`

$m_{i’}$ should still be mappable to P. there should exist at least one common location for $m_{i}$ and $m_{i’}$ `Source input:`

T,P,e `Source output:`

$T_{m_{1}}$ `Follow-up input:`

T,P,e, a subset M($m_{1},m_{2},\dots,m_{i}$) of $T_{m_{1}}$, L as one of M’s mismatch numbers `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

Arbitrarily replace several mismatches by different types of mismatch on $m_{i}$ (denoted as $m_{i’}$), while keeping the same total number of mismatches as L `Output relation:`

$m_{i’}$ should still be mappable to P. there should exist at least one common location for $m_{i}$ and $m_{i’}$ `Pattern:`

`Description:`

`Property:`

All reads in T that are mappable to P should also be mappable to P' `Source input:`

T,P `Source output:`

$T_{m_{1}}$ `Follow-up input:`

T,P’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

P’: Select a subset of sequence reads $TS \subset T$ and concatenate this subset of reads to the end of P `Output relation:`

All reads in T that are mappable to P should also be mappable to P' `Pattern:`

`Description:`

`Property:`

Each read in TS that is mappable to P should have at least one additional mapping location in the part of P', which corresponds to the concatenated string `Source input:`

T,P `Source output:`

$T_{m_{1}}$ `Follow-up input:`

T,P’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

P’: Select a subset of sequence reads $TS \subset T$ and concatenate this subset of reads to the end of P `Output relation:`

Each read in TS that is mappable to P should have at least one additional mapping location in the part of P', which corresponds to the concatenated string `Pattern:`

`Description:`

`Property:`

Each read in TS that is unmappable to P should be mapped at least once in the part of P', which corresponds to the concatenated string `Source input:`

T,P `Source output:`

$T_{m_{1}}$ `Follow-up input:`

T,P’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

P’: Select a subset of sequence reads $TS \subset T$ and concatenate this subset of reads to the end of P `Output relation:`

Each read in TS that is unmappable to P should be mapped at least once in the part of P', which corresponds to the concatenated string `Pattern:`

`Description:`

`Property:`

All reads in T that are unmappable top should also be unmappable to P' `Source input:`

T,P `Source output:`

$T_{m_{1}}$ `Follow-up input:`

T,P’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

P’: Deleting an arbitrary portion of either the beginning or ending of P `Output relation:`

All reads in T that are unmappable top should also be unmappable to P' `Pattern:`

`Description:`

`Property:`

$t_{i}$ is mappable to P if and only if $t_{i’}$ is mappable to P' for $1 \leq i \leq n$ `Source input:`

$T(t_{1},t_{2}, \dots ,t_{n})$,P `Source output:`

$T_{m_{1}}$ `Follow-up input:`

$T’(t_{1’},t_{2’}, \dots ,t_{n’})$,P’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

$t_{i’}$ is a reversed string of $t_{i’}$ for $1 \leq i \leq n$, and P' is a reversed string of P `Output relation:`

$t_{i}$ is mappable to P if and only if $t_{i’}$ is mappable to P' for $1 \leq i \leq n$ `Pattern:`

`Description:`

`Property:`

$t_{i}$ is unmappable to P if and only if $t_{i’}$ is unmappable to P' for $1 \leq i \leq n$ `Source input:`

$T(t_{1},t_{2}, \dots ,t_{n})$,P `Source output:`

$T_{m_{1}}$ `Follow-up input:`

$T’(t_{1’},t_{2’}, \dots ,t_{n’})$,P’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

$t_{i’}$ is a reversed string of $t_{i}$ for $1 \leq i \leq n$, and P' is a reversed string of P `Output relation:`

$t_{i}$ is unmappable to P if and only if $t_{i’}$ is unmappable to P' for $1 \leq i \leq n$ `Pattern:`

`Description:`

`Property:`

$t_{i}$ is mappable to P if and only if $t_{i’}$ is mappable to P' for $1 \leq i \leq n$ `Source input:`

$T(t_{1},t_{2}, \dots ,t_{n})$,P `Source output:`

$T_{m_{1}}$ `Follow-up input:`

$T’(t_{1’},t_{2’}, \dots ,t_{n’})$,P’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

$t_{i’}$=Permute($t_{i}$) for all $1 \leq i \leq n$, P' = Permute(P). `Output relation:`

$t_{i}$ is mappable to P if and only if $t_{i’}$ is mappable to P' for $1 \leq i \leq n$ `Pattern:`

`Description:`

One-to-One permutation function on the set of alphabets, Permute `Property:`

$t_{i}$ is unmappable to P if and only if $t_{i’}$ is unmappable to P' for $1 \leq i \leq n$ `Source input:`

$T(t_{1},t_{2}, \dots ,t_{n})$,P `Source output:`

$T_{m_{1}}$ `Follow-up input:`

$T’(t_{1’},t_{2’}, \dots ,t_{n’})$,P’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

$t_{i’}$=Permute($t_{i}$) for all $1 \leq i \leq n$, P' = Permute(P). `Output relation:`

$t_{i}$ is unmappable to P if and only if $t_{i’}$ is unmappable to P' for $1 \leq i \leq n$ `Pattern:`

`Description:`

`Property:`

$T_{m_{2}} \subset T_{m_{1}}$ `Source input:`

T,P,e `Source output:`

$T_{m_{1}}$ `Follow-up input:`

T,P,e’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

e’: $0<e’<e$ `Output relation:`

$T_{m_{2}} \subset T_{m_{1}}$ `Pattern:`

`Description:`

`Property:`

$T_{m_{1}} \subset T_{m_{2}}$ `Source input:`

T,P,e `Source output:`

$T_{m_{1}}$ `Follow-up input:`

T,P,e’ `Follow-up output:`

$T_{m_{2}}$ `Input relation:`

e’:$0<e<e’$ `Output relation:`

$T_{m_{1}} \subset T_{m_{2}}$ `Pattern:`