Bioinformatics/Global alignment: Difference between revisions

From Rosetta Code
Content added Content deleted
m (Thundergnat moved page Bioinformatics/global alignment to Bioinformatics/Global alignment: Standardize capitalization)
(→‎{{header|Perl}}: added Pascal by prepending to perl)
Line 807: Line 807:
————————————————————
————————————————————
Total length 300</pre>
Total length 300</pre>

=={{header|Pascal}}==
Used a matrix of head-tail overlapping and modified n-queens to generate the permutations.<BR>
Here nearly no runtime.But see [[N-queens_problem]] that using permutation is not the way for > 17<BR>
Of course this is more a traveling salesman problem.
<lang pascal>
program BaseInDNA;
{$IFDEF FPC}
{$mode Delphi} {$Optimization ON,All}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils,classes;
type
tmyString = AnsiString;//[255];
tpMyString = ^tmyString;
tOvrLapMat = array of array of Int32;
tNextDNA = array of Int32;
tpNextDNA = pInt32;
const
convDgtBase :array['1'..'5'] of char = ('A','C','G','T','U');

Test1 : array[0..4] of tmyString = ('TA','AAG','TA','GAA','TA');
Test2 : array[0..3] of tmyString = ('CATTAGGG', 'ATTAG', 'GGG', 'TA');
Test3 : array[0..2] of tmyString = ('AAGAUGGA', 'GGAGCGCAUC', 'AUCGCAAUAAGGA');
Test4 : array[0..12] of tmyString =
('ATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTAT',
'GGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGT',
'CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA',
'TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC',
'AACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTT',
'GCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTC',
'CGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCT',
'TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC',
'CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGC',
'GATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATT',
'TTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC',
'CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA',
'TCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGA');
var
sl_DNA : TStringList;
OverlapMat : tOvrLapMat;
SolDNA : tNextDNA;
pNextDNA : tpNextDNA;
DNA_Count,MAX,LastMax : Int32;

function ConvertACGT_1234(const s:AnsiString):AnsiString;
const
conv :array['A'..'U'] of char = ('1',#0,'2',#0,#0,#0,'3',#0,#0,
#0,#0,#0,#0,#0,#0,#0,#0,#0,
#0,'4','5');
var
pC: pChar;
i : NativeInt;
begin
i := Length(s);
setlength(result,i);
pC := @result[1];
dec(i);
while i >= 0 do
Begin
pC[i] := conv[s[i+1]];
dec(i);
end;
end;

function Convert1234_ACGTU(const s:AnsiString):AnsiString;
var
pC: pChar;
i : NativeInt;
begin
i := Length(s);
setlength(result,i);
pC := @result[1];
dec(i);
while i >= 0 do
Begin
pC[i] := convDgtBase[s[i+1]];
dec(i);
end;
end;

procedure Check_Base_Count(const s: ANsiString);
var
bc : ANsiString;
BaseCnt : array[0..4] of UInt32;
pC: pChar;
i : NativeInt;
Begin
writeln('Total length : ',Length(s));
bc := ConvertACGT_1234(s);
FillChar(BaseCnt,SizeOf(BaseCnt),#0);
pC := @bc[1];
for i := length(bc)-1 downto 0 do
inc(BaseCnt[Ord(pC[i])-Ord('1')]);
For i := 0 to 4 do
write(convDgtBase[chr(i+49)],' : ',BaseCnt[i]:3,' ');
writeln;
end;

procedure extract_double(var sl : TStringList);
var
i,j : NativeInt;
begin
sl.sort;
for i := sl.count-2 downto 0 do
if sl[i] = sl[i+1] then
sl.delete(i+1);

i := sl.count-1;
repeat
For j := i-1 Downto 0 do
Begin
if (Pos(sl[j],sl[i]) >0) then
Begin
sl.delete(j);
i := sl.count;
BREAK;
end
else
if (Pos(sl[i],sl[j]) >0) then
Begin
sl.delete(i);
i := sl.count;
BREAK;
end;
end;
dec(i);
until i < 1;
end;

procedure InsertSL(var sl : TStringList;pS :tpMyString;cnt:NativeInt);
Begin
sl.clear;
while cnt > 0 do
Begin
sl.Append(pS^);
inc(pS);
dec(cnt);
end;
extract_double(sl);
sl.sort;
end;

function Check_Head_Tail(const s1,s2: AnsiString):NativeInt;
var
cH : AnsiChar;
i,j,k : NativeInt;
Begin
result := 0;
j := length(s1);
cH := s2[1];
repeat
if s1[j]= cH then
Begin
i:= 1;
k := j;
while (s1[k] = s2[i]) AND (k <= length(s1)) do
begin
inc(i);
inc(k);
end;
if k > length(s1) then
result := length(s1)-j+1;
end;
dec(j);
until j <1;
end;

function CreateOvrLapMat(const sl_DNA:TStringList):tOvrLapMat;
var
col,row,DNAlen : NativeInt;
begin
DNAlen := sl_DNA.Count;
setlength(result,DNAlen,DNAlen);

dec(DNAlen);
For row := DNAlen downto 0 do
For col := DNAlen downto 0 do
if row<>col then
result[row,col] := Check_Head_Tail(sl_DNA[row],sl_DNA[col]);
{//output of matrix
For row := 0 to DNAlen do
Begin
For col := 0 to DNAlen do
write(OverlapMat[row,col]:3);
writeln;
end;
}

end;

procedure SetQueen(Row,sum,lastIdx:NativeInt);
var
i,NextIdx,dSum : nativeInt;
begin
IF row <= DNA_Count-1 then
begin
For i := row to DNA_Count-1 do
begin
NextIdx := pNextDNA[i];pNextDNA[i] := pNextDNA[Row];pNextDNA[Row] := NextIdx;
dSum :=OverlapMat[lastidx,NextIdx];
sum += dSum;
SetQueen(Row+1,sum,NextIdx);
sum -= dSum;
pNextDNA[Row] := pNextDNA[i];pNextDNA[i] := NextIdx;
end;
end
else
begin
//solution found could be modified MAX<=sum for more solutions of same length
If MAX<sum then
Begin
MAX := sum;
// remember the way
for i := DNA_Count-1 downto 0 do
SolDNA[i+1] := pNextDNA[i];
end;
end;
end;

procedure Find;
var
col,row,i : NativeInt;
NextDNA : tNextDNA;
Combined : AnsiString;
Begin
DNA_Count := sl_DNA.count;

IF DNA_Count = 1 then
Combined := sl_DNA[0]
else
Begin
setlength(SolDNA,DNA_count);
dec(DNA_Count);
setlength(NextDNA,DNA_count);

//Tail-Head-Matrix
OverlapMat := CreateOvrLapMat(sl_DNA);

MAX := 0;
LastMax := 0;
pNextDNA := @NextDNA[0];
//start with base_sequence[row]
for row := 0 to DNA_count do
begin
i := 0;
For col := 0 to DNA_count do
if row<>col then
begin
pNextDNA[i] := col;
inc(i);
end;

SetQueen(0,0,row);

If LastMax< MAX then
begin
SolDNA[0]:= row;
LastMax := MAX;
end;
end;
Combined := '';
for col := 0 to DNA_Count-1 do
Begin
write(SolDNA[col]+1,'->');
row := length(sl_DNA[SolDNA[col]]);
Combined += copy(sl_DNA[SolDNA[col]],1,row-OverlapMat[SolDNA[col],SolDNA[col+1]]);
end;
writeln(SolDNA[DNA_Count]+1);
Combined += sl_DNA[SolDNA[DNA_Count]];

LastMax := 0;
for col := 0 to DNA_Count do
inc(LastMax,Length(sl_DNA[col]));
IF LastMax-MAX <> length(combined) then
writeln(LastMax,'-',Max,' = ',LastMax-MAX,' ?=? ',length(combined));
end;
writeln(combined);
Check_Base_Count(combined);
writeln;
end;


BEGIN
sl_DNA := TStringList.create;
InsertSL(sl_DNA,@Test1[0],High(Test1)+1);
find;
InsertSL(sl_DNA,@Test2[0],High(Test2)+1);
find;
InsertSL(sl_DNA,@Test3[0],High(Test3)+1);
find;
InsertSL(sl_DNA,@Test4[0],High(Test4)+1);
find;
END.
</lang>
{{out}}
<pre>
2->1->3
GAAGTA
Total length : 6
A : 3 C : 0 G : 2 T : 1 U : 0

CATTAGGG
Total length : 8
A : 2 C : 1 G : 3 T : 2 U : 0

1->3->2
AAGAUGGAGCGCAUCGCAAUAAGGA
Total length : 25
A : 10 C : 4 G : 8 T : 0 U : 3

1->6->7->5->4->2->3
CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA
Total length : 300
A : 74 C : 57 G : 75 T : 94 U : 0
</pre>


=={{header|Perl}}==
=={{header|Perl}}==
Line 907: Line 1,225:
{ A => 74, C => 57, G => 75, T => 94 }
{ A => 74, C => 57, G => 75, T => 94 }
</pre>
</pre>



=={{header|Phix}}==
=={{header|Phix}}==

Revision as of 07:39, 11 August 2021

Bioinformatics/Global alignment is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Global alignment is designed to search for highly similar regions in two or more DNA sequences, where the sequences appear in the same order and orientation, fitting the sequences in as pieces in a puzzle.

Current DNA sequencers find the sequence for multiple small segments of DNA which have mostly randomly formed by splitting a much larger DNA molecule into shorter segments. When re-assembling such segments of DNA sequences into a larger sequence to form, for example, the DNA coding for the relevant gene, the overlaps between multiple shorter sequences are commonly used to decide how the longer sequence is to be assembled. For example, "AAGATGGA", GGAGCGCATC", and "ATCGCAATAAGGA" can be assembled into the sequence "AAGATGGAGCGCATCGCAATAAGGA" by noting that "GGA" is at the tail of the first string and head of the second string and "ATC" likewise is at the tail of the second and head of the third string.

When looking for the best global alignment in the output strings produced by DNA sequences, there are typically a large number of such overlaps among a large number of sequences. In such a case, the ordering that results in the shortest common superstring is generrally preferred.

Finding such a supersequence is an NP-hard problem, and many algorithms have been proposed to shorten calculations, especially when many very long sequences are matched.

The shortest common superstring as used in bioinfomatics here differs from the string task Shortest_common_supersequence. In that task, a supersequence may have other characters interposed as long as the characters of each subsequence appear in order, so that (abcbdab, abdcaba) -> abdcabdab. In this task, (abcbdab, abdcaba) -> abcbdabdcaba.


Task
  •   Given N non-identical strings of characters A, C, G, and T representing N DNA sequences, find the shortest DNA sequence containing all N sequences.
  •   Handle cases where two sequences are identical or one sequence is entirely contained in another.
  •   Print the resulting sequence along with its size (its base count) and a count of each base in the sequence.
  •   Find the shortest common superstring for the following four examples:
 
("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")
Related tasks




11l

Translation of: Nim

<lang 11l>-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)</lang>
Output:

Nucleotide counts for GAAGTA:

         A           3
         C           0
         G           2
         T           1
     Other           0
  --------------------
  Total length       6

Nucleotide counts for CATTAGGG:

         A           2
         C           1
         G           3
         T           2
     Other           0
  --------------------
  Total length       8

Nucleotide counts for AAGAUGGAGCGCAUCGCAAUAAGGA:

         A          10
         C           4
         G           8
         T           0
     Other           3
  --------------------
  Total length      25

Nucleotide counts for CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA:

         A          74
         C          57
         G          75
         T          94
     Other           0
  --------------------
  Total length     300

Go

Translation of: Julia

<lang go>package main

import ( 

   "fmt"
   "strings"

)

/* Gets n! for small n. */ func factorial(n int) int { 

   fact := 1
   for i := 2; i <= n; i++ {
       fact *= i
   }
   return fact

}

/* Gets all permutations of a list of strings. */ func getPerms(input []string) [][]string { 

   perms := [][]string{input}
   le := len(input)
   a := make([]string, le)
   copy(a, input)
   n := le - 1
   fact := factorial(n + 1)

   for c := 1; c < fact; c++ {
       i := n - 1
       j := n
       for i >= 0 && a[i] > a[i+1] {
           i--
       }
       if i == -1 {
           i = n
       }
       for a[j] < a[i] {
           j--
       }
       a[i], a[j] = a[j], a[i]
       j = n
       i++
       if i == n+1 {
           i = 0
       }
       for i < j {
           a[i], a[j] = a[j], a[i]
           i++
           j--
       }
       b := make([]string, le)
       copy(b, a)
       perms = append(perms, b)
   }
   return perms

}

/* Returns all distinct elements from a list of strings. */ func distinct(slist []string) []string { 

   distinctSet := make(map[string]int, len(slist))
   i := 0
   for _, s := range slist {
       if _, ok := distinctSet[s]; !ok {
           distinctSet[s] = i
           i++
       }
   }
   result := make([]string, len(distinctSet))
   for s, i := range distinctSet {
       result[i] = s
   }
   return result

}

/* Given a DNA sequence, report the sequence, length and base counts. */ func printCounts(seq string) { 

   bases := [][]rune{{'A', 0}, {'C', 0}, {'G', 0}, {'T', 0}}
   for _, c := range seq {
       for _, base := range bases {
           if c == base[0] {
               base[1]++
           }
       }
   }
   sum := 0
   fmt.Println("\nNucleotide counts for", seq, "\b:\n")
   for _, base := range bases {
       fmt.Printf("%10c%12d\n", base[0], base[1])
       sum += int(base[1])
   }
   le := len(seq)
   fmt.Printf("%10s%12d\n", "Other", le-sum)
   fmt.Printf("  ____________________\n%14s%8d\n", "Total length", le)

}

/* Return the position in s1 of the start of overlap of tail of string s1 with head of string s2. */ func headTailOverlap(s1, s2 string) int { 

   for start := 0; ; start++ {
       ix := strings.IndexByte(s1[start:], s2[0])
       if ix == -1 {
           return 0
       } else {
           start += ix
       }
       if strings.HasPrefix(s2, s1[start:]) {
           return len(s1) - start
       }
   }

}

/* Remove duplicates and strings contained within a larger string from a list of strings. */ func deduplicate(slist []string) []string { 

   var filtered []string
   arr := distinct(slist)
   for i, s1 := range arr {
       withinLarger := false
       for j, s2 := range arr {
           if j != i && strings.Contains(s2, s1) {
               withinLarger = true
               break
           }
       }
       if !withinLarger {
           filtered = append(filtered, s1)
       }
   }
   return filtered

}

/* Returns shortest common superstring of a list of strings. */ func shortestCommonSuperstring(slist []string) string { 

   ss := deduplicate(slist)
   shortestSuper := strings.Join(ss, "")
   for _, perm := range getPerms(ss) {
       sup := perm[0]
       for i := 0; i < len(ss)-1; i++ {
           overlapPos := headTailOverlap(perm[i], perm[i+1])
           sup += perm[i+1][overlapPos:]
       }
       if len(sup) < len(shortestSuper) {
           shortestSuper = sup
       }
   }
   return shortestSuper

}

func main() { 

   testSequences := [][]string{
       {"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",
       },
   }

   for _, test := range testSequences {
       scs := shortestCommonSuperstring(test)
       printCounts(scs)
   }

}</lang>

Output:
Nucleotide counts for TAAGAA:

         A           4
         C           0
         G           1
         T           1
     Other           0
  ____________________
  Total length       6

Nucleotide counts for CATTAGGG:

         A           2
         C           1
         G           3
         T           2
     Other           0
  ____________________
  Total length       8

Nucleotide counts for AAGAUGGAGCGCAUCGCAAUAAGGA:

         A          10
         C           4
         G           8
         T           0
     Other           3
  ____________________
  Total length      25

Nucleotide counts for CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA:

         A          74
         C          57
         G          75
         T          94
     Other           0
  ____________________
  Total length     300

jq

Works with: jq

Works with gojq, the Go implementation of jq <lang jq>

      1. Generic helper functions
  1. bag-of-words

def bow(stream): 

 reduce stream as $word ({}; .[($word|tostring)] += 1);

def permutations: 

 if length == 0 then []
 else
   range(0;length) as $i
   | [.[$i]] + (del(.[$i])|permutations)
 end ;</lang><lang jq>
  1. Give a synoptic view of the input string,
  2. highlighting the occurrence of ACGTU letters

def synopsis: 

 ["A", "C", "G", "T", "U"] as $standard
 | . as $seq
 | bow(explode | map([.]|implode)[]) as $bases
 | ("Nucleotide counts for \($seq):\n"),
   (($standard + ($bases|keys - $standard))[] | "\(.): \($bases[.]//0)"),
   "__",
   "Σ: \($seq|length)" ;
  1. If the strings, $s1 and $s2, overlap by at least $minimumoverlap characters,
  2. return { i1: <index in $s1 where overlap starts>, overlap: <overlapping string>},
  3. otherwise, return null

def overlap_info($s1; $s2; $minimumoverlap): 

 first( range(0; $s1|length + 1 - $minimumoverlap) as $i1
        | $s1[$i1:] as $overlap
        | select($s2 | startswith($overlap))

| {$i1, $overlap} ) // null ;

  1. Input: an array of strings
  2. Remove duplicates and strings contained within a larger string

def deduplicate: 

 unique
 | . as $arr
 | reduce range(0;length) as $i ([];
     $arr[$i] as $s1
     | if any( $arr[] | select(. != $s1); index($s1))
       then .

else . + [$s1] end);

  1. Given an array of deduplicated strings, attempt to find a superstring
  2. composed of these strings in the same order;
  3. return it if found, else null.

def relevant($min): 

 . as $in
 | length as $length
 | {s: .[0], i:0}
 | until (.s == null or .i >= $length - 1;
      .i as $i
      # Since the strings have been deduplicated we can use $in[$i]:
      | overlap_info($in[$i]; $in[$i+1]; $min) as $overlap
      | if $overlap then .s += $in[$i+1][$overlap.overlap|length:]
        else .s = null

end 

      | .i += 1 )
  | .s ;
  1. Input: an array of strings
  2. Return shortest common superstring

def shortest_common_superstring: 

 deduplicate as $ss
 | reduce ($ss | permutations) as $perm ({shortestsuper: ($ss | add) };
     ($perm | relevant(1)) as $candidate
     | if $candidate and ($candidate|length) < (.shortestsuper|length)
       then .shortestsuper = $candidate
       else . end)
 | .shortestsuper;

</lang> The specific tasks <lang jq> def examples: 

[
 ["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"]
 ];

def tasks: 

 def t: shortest_common_superstring | synopsis;

 examples
 | . as $examples
 | range(0;length) as $i
 |  "Task \($i+1):", ($examples[$i]|t), "";

tasks</lang>

Output:
Task 1:
Nucleotide counts for TAAGAA:

A: 4
C: 0
G: 1
T: 1
U: 0
__
Σ: 6

Task 2:
Nucleotide counts for CATTAGGG:

A: 2
C: 1
G: 3
T: 2
U: 0
__
Σ: 8

Task 3:
Nucleotide counts for AAGAUGGAGCGCAUCGCAAUAAGGA:

A: 10
C: 4
G: 8
T: 0
U: 3
__
Σ: 25

Task 4:
Nucleotide counts for CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA:

A: 74
C: 57
G: 75
T: 94
U: 0
__
Σ: 300

Julia

<lang julia>using Combinatorics

""" Given a DNA sequence, report the sequence, length and base counts""" function printcounts(seq) 

   bases = [['A', 0], ['C', 0], ['G', 0], ['T', 0]]
   for c in seq, base in bases
       if c == base[1]
           base[2] += 1
       end
   end
   println("\nNucleotide counts for $seq:\n")
   for base in bases
       println(lpad(base[1], 10), lpad(string(base[2]), 12))
   end
   println(lpad("Other", 10), lpad(string(length(seq) - sum(x[2] for x in bases)), 12))
   println("     _________________\n", lpad("Total length", 14), lpad(string(length(seq)), 8))

end

"""Return the position in s1 of the start of overlap of tail of string s1 with head of string s2""" function headtailoverlap(s1, s2, minimumoverlap=1) 

   start = 1
   while true
       range = findnext(s2[1:minimumoverlap], s1, start)
       range == nothing && return 0
       start = range.start
       startswith(s2, s1[start:end]) && return length(s1) - start + 1
       start += 1
   end

end

"""Remove duplicates and strings contained within a larger string from vector of strings""" function deduplicate(svect) 

   filtered = empty(svect)
   arr = unique(svect)
   for (i, s1) in enumerate(arr)
       any(p -> p[1] != i && occursin(s1, p[2]), enumerate(arr)) && continue
       push!(filtered, s1)
   end
   return filtered

end

"""Returns shortest common superstring of a vector of strings""" function shortest_common_superstring(svect) 

   ss = deduplicate(svect)
   shortestsuper = prod(ss)
   for perm in permutations(ss)
       sup = first(perm)
       for i in 1:length(ss)-1
           overlap_position = headtailoverlap(perm[i], perm[i+1], 1)
           sup *= perm[i + 1][overlap_position+1:end]
       end
       if length(sup) < length(shortestsuper)
           shortestsuper = sup
       end
   end
   return shortestsuper

end

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"] ]

for test in testsequences 

   scs = shortest_common_superstring(test)
   printcounts(scs)

end

</lang>

Output:
Nucleotide counts for TAAGAA:

         A           4
         C           0
         G           1
         T           1
     Other           0
     _________________
  Total length       6

Nucleotide counts for CATTAGGG:

         A           2
         C           1
         G           3
         T           2
     Other           0
     _________________
  Total length       8

Nucleotide counts for AAGAUGGAGCGCAUCGCAAUAAGGA:

         A          10
         C           4
         G           8
         T           0
     Other           3
     _________________
  Total length      25

Nucleotide counts for CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA:

         A          74
         C          57
         G          75
         T          94
     Other           0
     _________________
  Total length     300

Nim

Translation of: Wren

<lang Nim>import algorithm, sequtils, strformat, strutils, tables

const ACGT = ['A', 'C', 'G', 'T'] # Four DNA bases.

iterator permutations(slist: seq[string]): seq[string] = 

 var slist = sorted(slist)
 yield slist
 while slist.nextPermutation():
   yield slist


proc printCounts(dnaSeq: string) = 

 ## Given a DNA sequence, report the sequence, length and base counts.
 let counts = dnaSeq.toCountTable()
 echo &"\nNucleotide counts for {dnaSeq}:\n"
 for base in ACGT:
   echo &"{($base):>10} {counts[base]:11}"
 var others = 0
 for base in counts.keys:
   if base notin ACGT: inc others, counts[base]
 echo &"     Other {others:11}"
 echo &"  ————————————————————"
 echo &"  Total length {dnaSeq.len: 7}"


func headTailOverlap(s1, s2: string): int = 

 ## Return the position in "s1" of the start of overlap
 ## of tail of string "s1" with head of string "s2".
 var start = 0
 while true:
   start = s1.find(s2[0], start)
   if start < 0: return 0
   if s2.startsWith(s1[start..^1]): return s1.len - start
   inc start


proc deduplicate(slist: seq[string]): seq[string] = 

 ## Remove duplicates and strings contained within a larger string from a list of strings.
 let slist = sequtils.deduplicate(slist)
 for i, s1 in slist:
   block check:
     for j, s2 in slist:
       if j != i and s1 in s2:
         break check
     # "s1" is not contained in another string.
     result.add s1


func shortestCommonSuperstring(slist: seq[string]): string = 

 ## Return shortest common superstring of a list of strings.

 let slist = slist.deduplicate()
 result = slist.join()
 for perm in slist.permutations():
   var sup = perm[0]
   for i in 0..<slist.high:
     let overlapPos = headTailOverlap(perm[i], perm[i+1])
     sup &= perm[i+1][overlapPos..^1]
   if sup.len < result.len: result = sup


const 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"]]

for test in TestSequences: 

 let scs = test.shortestCommonSuperstring
 scs.printCounts()</lang>
Output:
Nucleotide counts for GAAGTA:

         A           3
         C           0
         G           2
         T           1
     Other           0
  ————————————————————
  Total length       6

Nucleotide counts for CATTAGGG:

         A           2
         C           1
         G           3
         T           2
     Other           0
  ————————————————————
  Total length       8

Nucleotide counts for AAGAUGGAGCGCAUCGCAAUAAGGA:

         A          10
         C           4
         G           8
         T           0
     Other           3
  ————————————————————
  Total length      25

Nucleotide counts for CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA:

         A          74
         C          57
         G          75
         T          94
     Other           0
  ————————————————————
  Total length     300

Pascal

Used a matrix of head-tail overlapping and modified n-queens to generate the permutations.
Here nearly no runtime.But see N-queens_problem that using permutation is not the way for > 17
Of course this is more a traveling salesman problem. <lang pascal> program BaseInDNA; {$IFDEF FPC} 

 {$mode Delphi}  {$Optimization ON,All}

{$ELSE} 

 {$APPTYPE CONSOLE}

{$ENDIF} uses 

 sysutils,classes;

type 

 tmyString = AnsiString;//[255];
 tpMyString = ^tmyString;
 tOvrLapMat = array of array of Int32;
 tNextDNA = array of Int32;
 tpNextDNA = pInt32;

const 

 convDgtBase :array['1'..'5'] of char = ('A','C','G','T','U');

 Test1 : array[0..4] of tmyString = ('TA','AAG','TA','GAA','TA');
 Test2 : array[0..3] of tmyString = ('CATTAGGG', 'ATTAG', 'GGG', 'TA');
 Test3 : array[0..2] of tmyString = ('AAGAUGGA', 'GGAGCGCAUC', 'AUCGCAAUAAGGA');
 Test4 : array[0..12] of tmyString =

('ATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTAT', 'GGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGT', 'CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA', 'TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC', 'AACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTT', 'GCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTC', 'CGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCT', 'TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC', 'CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGC', 'GATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATT', 'TTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC', 'CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA', 'TCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGA'); var 

 sl_DNA : TStringList;
 OverlapMat : tOvrLapMat;
 SolDNA : tNextDNA;
 pNextDNA : tpNextDNA;
 DNA_Count,MAX,LastMax : Int32;

function ConvertACGT_1234(const s:AnsiString):AnsiString; const 

 conv :array['A'..'U'] of char = ('1',#0,'2',#0,#0,#0,'3',#0,#0,
                                  #0,#0,#0,#0,#0,#0,#0,#0,#0,
                                  #0,'4','5');

var 

 pC: pChar;
 i : NativeInt;

begin 

 i := Length(s);
 setlength(result,i);
 pC := @result[1];
 dec(i);
 while i >= 0 do
 Begin
   pC[i] := conv[s[i+1]];
   dec(i);
 end;

end;

function Convert1234_ACGTU(const s:AnsiString):AnsiString; var 

 pC: pChar;
 i : NativeInt;

begin 

 i := Length(s);
 setlength(result,i);
 pC := @result[1];
 dec(i);
 while i >= 0 do
 Begin
   pC[i] := convDgtBase[s[i+1]];
   dec(i);
 end;

end;

procedure Check_Base_Count(const s: ANsiString); var 

 bc : ANsiString;
 BaseCnt : array[0..4] of UInt32;
 pC: pChar;
 i : NativeInt;

Begin 

 writeln('Total length : ',Length(s));
 bc := ConvertACGT_1234(s);
 FillChar(BaseCnt,SizeOf(BaseCnt),#0);
 pC := @bc[1];
 for i := length(bc)-1 downto 0 do
   inc(BaseCnt[Ord(pC[i])-Ord('1')]);
 For i := 0 to 4 do
   write(convDgtBase[chr(i+49)],' : ',BaseCnt[i]:3,'  ');
 writeln;

end;

procedure extract_double(var sl : TStringList); var 

 i,j : NativeInt;

begin 

 sl.sort;
 for i := sl.count-2 downto 0 do
   if sl[i] = sl[i+1] then
     sl.delete(i+1);

 i := sl.count-1;
 repeat
   For j := i-1 Downto 0 do
   Begin
     if (Pos(sl[j],sl[i]) >0) then
     Begin
       sl.delete(j);
       i := sl.count;
       BREAK;
     end
     else
       if (Pos(sl[i],sl[j]) >0) then
       Begin
         sl.delete(i);
       i := sl.count;
       BREAK;
       end;
   end;
   dec(i);
 until i < 1;

end;

procedure InsertSL(var sl : TStringList;pS :tpMyString;cnt:NativeInt); Begin 

 sl.clear;
 while cnt > 0 do
 Begin
   sl.Append(pS^);
   inc(pS);
   dec(cnt);
 end;
 extract_double(sl);
 sl.sort;

end;

function Check_Head_Tail(const s1,s2: AnsiString):NativeInt; var 

 cH : AnsiChar;
 i,j,k : NativeInt;

Begin 

 result := 0;
 j := length(s1);
 cH := s2[1];
 repeat
   if s1[j]= cH then
   Begin
     i:= 1;
     k := j;
     while (s1[k] = s2[i]) AND (k <= length(s1)) do
     begin
       inc(i);
       inc(k);
     end;
     if k > length(s1) then
       result := length(s1)-j+1;
   end;
   dec(j);
 until j <1;

end;

function CreateOvrLapMat(const sl_DNA:TStringList):tOvrLapMat; var 

 col,row,DNAlen : NativeInt;

begin 

 DNAlen := sl_DNA.Count;
 setlength(result,DNAlen,DNAlen);

 dec(DNAlen);
 For row := DNAlen downto 0 do
   For col := DNAlen downto 0 do
     if row<>col then
       result[row,col] := Check_Head_Tail(sl_DNA[row],sl_DNA[col]);

{//output of matrix 

 For row := 0 to DNAlen do
 Begin
   For col := 0 to DNAlen do
     write(OverlapMat[row,col]:3);
   writeln;
 end;

}

end;

procedure SetQueen(Row,sum,lastIdx:NativeInt); var 

 i,NextIdx,dSum : nativeInt;

begin 

 IF row <= DNA_Count-1 then
 begin
   For i := row to DNA_Count-1 do
   begin
     NextIdx := pNextDNA[i];pNextDNA[i] := pNextDNA[Row];pNextDNA[Row] := NextIdx;
     dSum :=OverlapMat[lastidx,NextIdx];
     sum += dSum;
       SetQueen(Row+1,sum,NextIdx);
     sum -= dSum;
     pNextDNA[Row] := pNextDNA[i];pNextDNA[i] := NextIdx;
   end;
 end
 else
 begin
   //solution found could be modified MAX<=sum for more solutions of same length
   If MAX<sum then
   Begin
     MAX := sum;
     // remember the way 
     for i := DNA_Count-1 downto 0 do
       SolDNA[i+1] := pNextDNA[i];
   end;
 end;

end;

procedure Find; var 

 col,row,i : NativeInt;
 NextDNA : tNextDNA;
 Combined : AnsiString;

Begin 

 DNA_Count := sl_DNA.count;

 IF DNA_Count = 1 then
   Combined := sl_DNA[0]
 else
 Begin
   setlength(SolDNA,DNA_count);
   dec(DNA_Count);
   setlength(NextDNA,DNA_count);

   //Tail-Head-Matrix
   OverlapMat := CreateOvrLapMat(sl_DNA);

   MAX := 0;
   LastMax := 0;
   pNextDNA := @NextDNA[0];
   //start with base_sequence[row]
   for row := 0 to DNA_count do
   begin
     i := 0;
     For col := 0 to DNA_count do
       if row<>col then
       begin
         pNextDNA[i] := col;
         inc(i);
       end;

       SetQueen(0,0,row);

      If LastMax< MAX then
      begin
        SolDNA[0]:= row;
        LastMax := MAX;
     end;
   end;
   Combined := ;
   for col := 0 to DNA_Count-1 do
   Begin
     write(SolDNA[col]+1,'->');
     row := length(sl_DNA[SolDNA[col]]);
     Combined += copy(sl_DNA[SolDNA[col]],1,row-OverlapMat[SolDNA[col],SolDNA[col+1]]);
   end;
   writeln(SolDNA[DNA_Count]+1);
   Combined += sl_DNA[SolDNA[DNA_Count]];

   LastMax := 0;
   for col := 0 to DNA_Count do
     inc(LastMax,Length(sl_DNA[col]));
   IF LastMax-MAX <> length(combined) then
     writeln(LastMax,'-',Max,' = ',LastMax-MAX,' ?=? ',length(combined));
 end;
 writeln(combined);
 Check_Base_Count(combined);
 writeln;

end;


BEGIN 

 sl_DNA := TStringList.create;
 InsertSL(sl_DNA,@Test1[0],High(Test1)+1);
 find;
 InsertSL(sl_DNA,@Test2[0],High(Test2)+1);
 find;
 InsertSL(sl_DNA,@Test3[0],High(Test3)+1);
 find;
 InsertSL(sl_DNA,@Test4[0],High(Test4)+1);
 find;

END. </lang>

Output:
2->1->3
GAAGTA
Total length : 6
A :   3  C :   0  G :   2  T :   1  U :   0

CATTAGGG
Total length : 8
A :   2  C :   1  G :   3  T :   2  U :   0

1->3->2
AAGAUGGAGCGCAUCGCAAUAAGGA
Total length : 25
A :  10  C :   4  G :   8  T :   0  U :   3

1->6->7->5->4->2->3
CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA
Total length : 300
A :  74  C :  57  G :  75  T :  94  U :   0

Perl

<lang perl>#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Bioinformatics/global_alignment use warnings; use List::Util qw( first uniq );

my @seq = ( 

 [ qw( TA AAG TA GAA TA ) ],

 [ qw( CATTAGGG ATTAG GGG TA) ],

 [ qw( AAGAUGGA GGAGCGCAUC AUCGCAAUAAGGA ) ],

 [ qw(
 ATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTAT
 GGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGT
 CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA
 TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC
 AACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTT
 GCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTC
 CGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCT
 TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC
 CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGC
 GATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATT
 TTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC
 CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA
 TCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGA
 ) ],
 );

sub removedups # remove dups and subseqs 

 {
 local $_ = join ' ', sort { length $a <=> length $b } split ' ', shift;
 1 while s/\b(\w+) (?=.*\1)//;
 return $_;
 }

for ( @seq ) 

 {
 local $_ = removedups join ' ', @$_;
 my @queue = $_;
 my @best;

 while( @queue )
   {
   local $_ = shift @queue;
   my @seq = split ' ', $_;
   my @over;
   for my $left ( @seq )
     {
     for my $right ( @seq )
       {
       $left eq $right and next;
       "$left $right" =~ /(.+) \1/ or next;
       my $len = length $1;
       $over[$len] .= "$left $right\n";
       }
     }
   if( @over )
     {
     for my $join ( split /\n/, $over[-1] )
       {
       my ($left, $right) = split ' ', $join;
       my @newseq = grep $_ ne $left && $_ ne $right, @seq; # remove used
       push @queue, removedups "$left $right" =~ s/(.+) (?=\1)//r .
         join ' ', , @newseq;
       }
     }
   else
     {
     tr/ //d;
     $best[length] .= "$_\n";
     next;
     }
   }

 for ( uniq split /\n/, first {defined} @best )
   {
   printf "\nlength %d - %s\n", length, $_;
   my %ch;
   $ch{$_}++ for /./g;
   use Data::Dump 'dd'; dd \%ch;
   }
 }</lang>
Output:
length 6 - TAGAAG
{ A => 3, G => 2, T => 1 }

length 8 - CATTAGGG
{ A => 2, C => 1, G => 3, T => 2 }

length 25 - AAGAUGGAGCGCAUCGCAAUAAGGA
{ A => 10, C => 4, G => 8, U => 3 }

length 300 - CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA
{ A => 74, C => 57, G => 75, T => 94 }

Phix

procedure printcounts(sequence ss)
-- Given DNA sequence(s), report the sequence, length and base counts
    for i=1 to length(ss) do
        string dna = ss[i]
        sequence acgt = repeat(0,6)
        for j=1 to length(dna) do
            acgt[find(dna[j],"ACGT")+1] += 1
        end for
        acgt[$] = sum(acgt)
        string ncf = "Nucleotide counts for :"
        printf(1,"%s%s\n",{ncf,join(split_by(dna,50),"\n"&repeat(' ',length(ncf)))})
        printf(1,"Base counts: Other:%d, A:%d, C:%d, G:%d, T:%d, total:%d\n\n",acgt)
    end for
end procedure
 
function deduplicate(sequence ss)
-- Remove any strings contained within a larger string from a set of strings
    sequence filtered = {}
    for i=1 to length(ss) do
        string si = ss[i]
        bool found = false
        for j=1 to length(ss) do
            if i!=j and match(si,ss[j]) then
                found = true
                exit
            end if
        end for
        if not found then
            filtered = append(filtered, si)
        end if
    end for
    return filtered
end function
 
procedure shortest_common_superstring(sequence ss)
-- Returns shortest common superstring of a set of strings
    ss = deduplicate(unique(ss))
    sequence shortestsuper = {join(ss,"")}
    integer shortest = length(shortestsuper[1])
    for p=1 to factorial(length(ss)) do
        sequence perm = permute(p,ss)
        string sup = perm[1]
        for i=2 to length(perm) do
            string pi = perm[i]
            for j=-min(length(pi),length(sup)) to 0 do
                string overlap = sup[j..$]
                if overlap = pi[1..length(overlap)] then
                    sup &= pi[length(overlap)+1..$]
                    pi = ""
                    exit
                end if
            end for
            if length(pi) then ?9/0 end if -- (sanity chk)
        end for
        if length(sup) < shortest then
            shortest = length(sup)
            shortestsuper = {sup}
        elsif length(sup) = shortest
          and not find(sup,shortestsuper) then
            shortestsuper = append(shortestsuper,sup)
        end if
    end for
    printcounts(shortestsuper)
end procedure
 
constant tests = {
{"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"}
}
papply(tests, shortest_common_superstring)
Output:

(Shows three length-6 results for the first test) 

Nucleotide counts for :TAAGAA
Base counts: Other:0, A:4, C:0, G:1, T:1, total:6

Nucleotide counts for :GAAGTA
Base counts: Other:0, A:3, C:0, G:2, T:1, total:6

Nucleotide counts for :TAGAAG
Base counts: Other:0, A:3, C:0, G:2, T:1, total:6

Nucleotide counts for :CATTAGGG
Base counts: Other:0, A:2, C:1, G:3, T:2, total:8

Nucleotide counts for :AAGAUGGAGCGCAUCGCAAUAAGGA
Base counts: Other:3, A:10, C:4, G:8, T:0, total:25

Nucleotide counts for :CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATG
                       CTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTG
                       AGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGAT
                       GGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTT
                       CGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGG
                       TCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA
Base counts: Other:0, A:74, C:57, G:75, T:94, total:300

Python

Translation of: Go

<lang python>import os

from collections import Counter from functools import reduce from itertools import permutations

BASES = ("A", "C", "G", "T")


def deduplicate(sequences): 

   """Return the set of sequences with those that are a substring
   of others removed too."""
   sequences = set(sequences)
   duplicates = set()

   for s, t in permutations(sequences, 2):
       if s != t and s in t:
           duplicates.add(s)

   return sequences - duplicates


def smash(s, t): 

   """Return `s` concatenated with `t`. The longest suffix of `s`
   that matches a prefix of `t` will be removed."""
   for i in range(len(s)):
       if t.startswith(s[i:]):
           return s[:i] + t
   return s + t


def shortest_superstring(sequences): 

   """Return the shortest superstring covering all sequences. If
   there are multiple shortest superstrings, an arbitrary
   superstring is returned."""
   sequences = deduplicate(sequences)
   shortest = "".join(sequences)

   for perm in permutations(sequences):
       superstring = reduce(smash, perm)
       if len(superstring) < len(shortest):
           shortest = superstring

   return shortest


def shortest_superstrings(sequences): 

   """Return a list of all shortest superstrings that cover
   `sequences`."""
   sequences = deduplicate(sequences)

   shortest = set(["".join(sequences)])
   shortest_length = sum(len(s) for s in sequences)

   for perm in permutations(sequences):
       superstring = reduce(smash, perm)
       superstring_length = len(superstring)
       if superstring_length < shortest_length:
           shortest.clear()
           shortest.add(superstring)
           shortest_length = superstring_length
       elif superstring_length == shortest_length:
           shortest.add(superstring)

   return shortest


def print_report(sequence): 

   """Writes a report to stdout for the given DNA sequence."""
   buf = [f"Nucleotide counts for {sequence}:\n"]

   counts = Counter(sequence)
   for base in BASES:
       buf.append(f"{base:>10}{counts.get(base, 0):>12}")

   other = sum(v for k, v in counts.items() if k not in BASES)
   buf.append(f"{'Other':>10}{other:>12}")

   buf.append(" " * 5 + "_" * 17)
   buf.append(f"{'Total length':>17}{sum(counts.values()):>5}")

   print(os.linesep.join(buf), "\n")


if __name__ == "__main__": 

   test_cases = [
       ("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",
       ),
   ]

   for case in test_cases:
       for superstring in shortest_superstrings(case):
           print_report(superstring)

   # or ..
   #
   # for case in test_cases:
   #     print_report(shortest_superstring(case))
   #
   # .. if you don't want all possible shortest superstrings.

</lang>

Output:
Nucleotide counts for GAAGTA:

         A           3
         C           0
         G           2
         T           1
     Other           0
     _________________
     Total length    6 

Nucleotide counts for TAAGAA:

         A           4
         C           0
         G           1
         T           1
     Other           0
     _________________
     Total length    6 

Nucleotide counts for TAGAAG:

         A           3
         C           0
         G           2
         T           1
     Other           0
     _________________
     Total length    6 

Nucleotide counts for CATTAGGG:

         A           2
         C           1
         G           3
         T           2
     Other           0
     _________________
     Total length    8 

Nucleotide counts for AAGAUGGAGCGCAUCGCAAUAAGGA:

         A          10
         C           4
         G           8
         T           0
     Other           3
     _________________
     Total length   25 

Nucleotide counts for CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA:

         A          74
         C          57
         G          75
         T          94
     Other           0
     _________________
     Total length  300

Raku

Translation of: Go
Translation of: Julia

<lang perl6># 20210209 Raku programming solution

sub printCounts(\seq) { 

  my $bases = seq.comb.Bag ;
  say "\nNucleotide counts for ", seq, " :";
  say $bases.kv, " and total length = ", $bases.total

}

sub stringCentipede(\s1, \s2) { 

  loop ( my $offset = 0, my \S1 = $ =  ; ; $offset++ ) {
     S1 = s1.substr: $offset ;
     with S1.index(s2.substr(0,1)) -> $p { $offset += $p } else { return False }
     return s1.chars - $offset if s2.starts-with: s1.substr: $offset
  }

}

sub deduplicate { 

  my @sorted = @_.unique.sort: *.chars; # by length   
  gather while ( my $target = shift @sorted ) {
     take $target unless @sorted.grep: { .contains: $target }  
  }

}

sub shortestCommonSuperstring { 

  my \ß = $ = [~] my @ss = deduplicate @_ ;           # ShortestSuper
  for @ss.permutations -> @perm {
     my \sup = $ = @perm[0];
     for @perm.rotor(2 => -1) { sup ~= @_[1].substr: stringCentipede |@_ }
     ß = sup if sup.chars < ß.chars ;
  }
  ß

}

.&shortestCommonSuperstring.&printCounts for ( 

  <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
  >,

) </lang>

Output:

Nucleotide counts for TAAGAA :
(T 1 A 4 G 1) and total length = 6

Nucleotide counts for CATTAGGG :
(G 3 A 2 T 2 C 1) and total length = 8

Nucleotide counts for AAGAUGGAGCGCAUCGCAAUAAGGA :
(A 10 U 3 C 4 G 8) and total length = 25

Nucleotide counts for CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA :
(C 57 G 75 A 74 T 94) and total length = 300

Wren

Translation of: Julia
Library: Wren-fmt
Library: Wren-seq
Library: Wren-str
Library: Wren-math

<lang ecmascript>import "/fmt" for Fmt import "/seq" for Lst import "/str" for Str import "/math" for Int

/* Gets all permutations of a list of strings. */ var getPerms = Fn.new { |input| 

   var perms = [input]
   var a = input.toList
   var n = a.count - 1
   for (c in 1...Int.factorial(n+1)) {
       var i = n - 1
       var j = n
       while (Str.gt(a[i], a[i+1])) i = i - 1
       while (Str.lt(a[j], a[i]))   j = j - 1
       var t = a[i]
       a[i] = a[j]
       a[j] = t
       j = n
       i = i + 1
       while (i < j) {
           t = a[i]
           a[i] = a[j]
           a[j] = t
           i = i + 1
           j = j - 1
       }
       perms.add(a.toList)
   }
   return perms

}

/* Given a DNA sequence, report the sequence, length and base counts. */ var printCounts = Fn.new { |seq| 

   var bases = [["A", 0], ["C", 0], ["G", 0], ["T", 0]]
   for (c in seq) {
       for (base in bases) {
           if (c == base[0]) base[1] = base[1] + 1
       }
   }
   System.print("\nNucleotide counts for %(seq):\n")
   for (base in bases) Fmt.print("$10s$12d", base[0], base[1])
   var sum = bases.reduce(0) { |acc, x| acc + x[1] }
   Fmt.print("$10s$12d", "Other", seq.count - sum)
   Fmt.print("  ____________________\n$14s$8d", "Total length", seq.count)

}

/* Return the position in s1 of the start of overlap of tail of string s1 with head of string s2. */ var headTailOverlap = Fn.new { |s1, s2| 

   var start = 0
   while (true) {
       start = s1.indexOf(s2[0], start)
       if (start == -1) return 0
       if (s2.startsWith(s1[start..-1])) return s1.count - start
       start = start + 1
   }

}

/* Remove duplicates and strings contained within a larger string from a list of strings. */ var deduplicate = Fn.new { |slist| 

   var filtered = []
   var arr = Lst.distinct(slist)
   var i = 0
   for (s1 in arr) {
       var j = 0
       var withinLarger = false
       for (s2 in arr) {
           if (j != i && s2.contains(s1)) {
               withinLarger = true
               break
           }
           j = j + 1
       }
       if (!withinLarger) filtered.add(s1)
       i = i + 1
   }
   return filtered

}

/* Returns shortest common superstring of a list of strings. */ var shortestCommonSuperstring = Fn.new { |slist| 

   var ss = deduplicate.call(slist)
   var shortestSuper = ss.join()
   for (perm in getPerms.call(ss)) {
       var sup = perm[0]
       for (i in 0...ss.count-1) {
           var overlapPos = headTailOverlap.call(perm[i], perm[i+1])
           sup = sup + perm[i+1][overlapPos..-1]
       }
       if (sup.count < shortestSuper.count) shortestSuper = sup
   }
   return shortestSuper

}

var 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"
   ]

]

for (test in testSequences) { 

   var scs = shortestCommonSuperstring.call(test)
   printCounts.call(scs)

}</lang>

Output:
Nucleotide counts for TAAGAA:

         A           4
         C           0
         G           1
         T           1
     Other           0
  ____________________
  Total length       6

Nucleotide counts for CATTAGGG:

         A           2
         C           1
         G           3
         T           2
     Other           0
  ____________________
  Total length       8

Nucleotide counts for AAGAUGGAGCGCAUCGCAAUAAGGA:

         A          10
         C           4
         G           8
         T           0
     Other           3
  ____________________
  Total length      25

Nucleotide counts for CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA:

         A          74
         C          57
         G          75
         T          94
     Other           0
  ____________________
  Total length     300
Retrieved from "https://rosettacode.org/wiki/Bioinformatics/Global_alignment?oldid=307702"