-
Notifications
You must be signed in to change notification settings - Fork 0
/
result.go
133 lines (115 loc) · 2.99 KB
/
result.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package align
import (
"fmt"
"io"
)
const (
gap = '-'
)
type Sequence []rune
func (s Sequence) reverse() {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
type alignment struct {
a Sequence
b Sequence
}
func (pair alignment) String() string {
return fmt.Sprintf("%s\n%s", string(pair.a), string(pair.b))
}
func (pair alignment) copyAdd(A, B rune) alignment {
copy := alignment{}
for i, _ := range pair.a {
copy.a = append(copy.a, pair.a[i])
copy.b = append(copy.b, pair.b[i])
}
copy.a = append(copy.a, A)
copy.b = append(copy.b, B)
return copy
}
type Result struct {
a Sequence
b Sequence
f scoreMatrix
}
func (m *Result) equal(i, j int) bool {
return m.a[i] == m.b[j]
}
func (result *Result) findAlignments(x, y int, pair alignment) (all []alignment) {
cell := result.f[y][x]
if cell.origin == 0 {
pair.a.reverse()
pair.b.reverse()
return append(all, pair)
}
A := result.a[x-1]
B := result.b[y-1]
if hasBit(cell.origin, diagOrigin) {
copy := pair.copyAdd(A, B)
all = append(all, result.findAlignments(x-1, y-1, copy)...)
}
if hasBit(cell.origin, leftOrigin) {
copy := pair.copyAdd(A, gap)
all = append(all, result.findAlignments(x-1, y, copy)...)
}
if hasBit(cell.origin, topOrigin) {
copy := pair.copyAdd(gap, B)
all = append(all, result.findAlignments(x, y-1, copy)...)
}
return all
}
// Score returns the score, ie. the max of the bottom right cell
func (result *Result) MaxScore() (score int) {
x := len(result.f[0]) - 1
y := len(result.f) - 1
return result.f[y][x].max
}
func hasBit(n int, pos uint) bool {
val := n & (1 << pos)
return (val > 0)
}
func (result *Result) PrintAlignment(w io.Writer) {
for _, p := range result.Alignments() {
fmt.Fprintf(w, "%s\n\n", p.String())
}
}
// Alignments returns all possible alignments with max score
func (result *Result) Alignments() []alignment {
x := len(result.f[0]) - 1
y := len(result.f) - 1
var pair alignment
return result.findAlignments(x, y, pair)
}
type valueReader func(c cell) int
// PrintScoreMatrix writes out the sequences and their calculated score as shown on wikipedia.
func (result *Result) PrintScoreMatrix(w io.Writer) {
result.printMatrix(func(c cell) int { return c.max }, w)
}
// PrintOrigins writes out the score origins for each score.
// 0 = None(top row and first column), 1 = Diagonal, 2 = Left and 4 = Top
// Eg. 5 = diagonal or top
func (result *Result) PrintOrigins(w io.Writer) {
result.printMatrix(func(c cell) int { return c.origin }, w)
}
func (result *Result) printMatrix(read valueReader, w io.Writer) {
// sequence a
fmt.Fprintf(w, "%4s", "")
for _, r := range result.a {
fmt.Fprintf(w, "%3v", string(r))
}
fmt.Fprint(w, "\n ")
// First row
for x := 0; x < len(result.f[0]); x++ {
fmt.Fprintf(w, "%3v", read(result.f[0][x]))
}
fmt.Fprint(w, "\n")
for y, row := range result.f[1:] {
fmt.Fprintf(w, "%s", string(result.b[y])) // sequence b
for x := 0; x < len(row); x++ {
fmt.Fprintf(w, "%3v", read(row[x]))
}
fmt.Fprint(w, "\n")
}
}