SeqMap

### Program Information

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}$

#### Reference

 An innovative approach for testing bioinformatics programs using metamorphic testing   10.1186/1471-2105-10-24

### MR Information

#### MR1------

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:

#### MR2------

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:

#### MR3------

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:

#### MR4------

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:

#### MR5------

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:

#### MR6------

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:

#### MR7------

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:

#### MR8------

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:

#### MR9------

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:

#### MR10------

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:

#### MR11------

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:

#### MR12------

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:

#### MR13------

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:
Insert title here