80 lines
2.7 KiB
Text
80 lines
2.7 KiB
Text
-V ACGT = [‘A’, ‘C’, ‘G’, ‘T’]
|
||
|
||
F permutations(slist)
|
||
V l = sorted(slist)
|
||
V r = [l]
|
||
L l.next_permutation()
|
||
r [+]= copy(l)
|
||
R r
|
||
|
||
F printCounts(dnaSeq)
|
||
DefaultDict[Char, Int] counts
|
||
L(c) dnaSeq
|
||
counts[c]++
|
||
print("\nNucleotide counts for #.:\n".format(dnaSeq))
|
||
L(base) :ACGT
|
||
print(‘#10 #11’.format(base, counts[base]))
|
||
V others = 0
|
||
L(base) counts.keys()
|
||
I base !C :ACGT
|
||
others += counts[base]
|
||
print(‘ Other #11’.format(others))
|
||
print(‘ --------------------’)
|
||
print(‘ Total length #7’.format(dnaSeq.len))
|
||
|
||
F headTailOverlap(s1, s2)
|
||
V start = 0
|
||
L
|
||
V? n = s1.find(s2[0], start)
|
||
I n == N
|
||
R 0
|
||
start = n
|
||
I s2.starts_with(s1[start..])
|
||
R s1.len - start
|
||
start++
|
||
|
||
F deduplicate(slist)
|
||
[String] r
|
||
V s = Set(slist)
|
||
L(s1) s
|
||
V i = L.index
|
||
L(s2) s
|
||
I L.index != i & s1 C s2
|
||
L.break
|
||
L.was_no_break
|
||
r.append(s1)
|
||
R r
|
||
|
||
F shortestCommonSuperstring(sl)
|
||
V slist = deduplicate(sl)
|
||
V result = slist.join(‘’)
|
||
L(perm) permutations(slist)
|
||
String sup = perm[0]
|
||
L(i) 0 .< slist.len - 1
|
||
V overlapPos = headTailOverlap(perm[i], perm[i + 1])
|
||
sup ‘’= perm[i + 1][overlapPos..]
|
||
I sup.len < result.len
|
||
result = sup
|
||
R result
|
||
|
||
V TestSequences = [
|
||
[‘TA’, ‘AAG’, ‘TA’, ‘GAA’, ‘TA’],
|
||
[‘CATTAGGG’, ‘ATTAG’, ‘GGG’, ‘TA’],
|
||
[‘AAGAUGGA’, ‘GGAGCGCAUC’, ‘AUCGCAAUAAGGA’],
|
||
[‘ATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTAT’,
|
||
‘GGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGT’,
|
||
‘CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA’,
|
||
‘TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC’,
|
||
‘AACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTT’,
|
||
‘GCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTC’,
|
||
‘CGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCT’,
|
||
‘TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC’,
|
||
‘CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGC’,
|
||
‘GATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATT’,
|
||
‘TTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC’,
|
||
‘CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA’,
|
||
‘TCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGA’]]
|
||
|
||
L(test) TestSequences
|
||
V scs = shortestCommonSuperstring(test)
|
||
printCounts(scs)
|