Rosetta Code

Bioinformatics/Global alignment: Difference between revisions

Page Discussion

Bioinformatics/Global alignment (view source)

Revision as of 09:33, 8 November 2023

24,336 bytes added ,  6 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(14 intermediate revisions by 6 users not shown)
Line 1:
{{task}}
{{Draft task}}[[Category:Bioinfomatics]][[Category:Strings]]
 
[[Category:Bioinfomatics]]
[[Category:Strings]]
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.
Line 53 ⟶ 55:
:* [[Bioinformatics/Sequence_mutation|Bioinformatics sequence mutation]].
<br><br>
=={{header|11l}}==
{{trans|Nim}}
 
<syntaxhighlight 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)</syntaxhighlight>
 
{{out}}
<pre>
 
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
</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">
 
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>
 
// Print a report of the given string to the standard output device.
void print_report(const std::string& text) {
std::unordered_map<char, int32_t> bases;
for ( const char& ch : text ) {
bases[ch]++;
}
 
const int32_t total = std::accumulate(bases.begin(), bases.end(), 0,
[&](int32_t previous_sum, std::pair<char, int32_t> entry) {
return previous_sum + entry.second;
});
 
std::cout << "Nucleotide counts for: " << ( ( text.length() > 50 ) ? "\n" : "" );
std::cout << text << std::endl;
std::cout << "Bases: A " << bases['A'] << ", C: " << bases['C'] << ", G: " << bases['G'] << ", T: " << bases['T']
<< ", total: " << total << "\n" << std::endl;
}
 
// Return all permutations of the given list of strings.
std::vector<std::vector<std::string>> permutations(std::vector<std::string>& list) {
int32_t indexes[list.size()] = {};
std::vector<std::vector<std::string>> result;
result.push_back(list);
int32_t i = 0;
while ( (uint64_t) i < list.size() ) {
if ( indexes[i] < i ) {
const int j = ( i % 2 == 0 ) ? 0 : indexes[i];
std::swap(list[i], list[j]);
result.push_back(list);
indexes[i]++;
i = 0;
} else {
indexes[i] = 0;
i++;
}
}
return result;
}
 
// Return 'before' concatenated with 'after', removing the longest suffix of 'before' that matches a prefix of 'after'.
std::string concatenate(const std::string& before, const std::string& after) {
for ( uint64_t i = 0; i < before.length(); ++i ) {
if ( after.starts_with(before.substr(i, before.length())) ) {
return before.substr(0, i) + after;
}
}
return before + after;
}
 
// Remove duplicate strings and strings which are substrings of other strings in the given list.
std::vector<std::string> deduplicate(const std::vector<std::string>& list) {
std::vector<std::string> singletons(list);
std::sort(singletons.begin(), singletons.end());
singletons.erase(std::unique(singletons.begin(), singletons.end()), singletons.end());
 
std::vector<std::string> result(singletons);
std::unordered_set<std::string> marked_for_removal;
for ( const std::string& test_word : result ) {
for ( const std::string& word : singletons ) {
if ( word != test_word && word.find(test_word) != std::string::npos ) {
marked_for_removal.emplace(test_word);
}
}
}
 
result.erase(std::remove_if(result.begin(), result.end(),
[&](std::string& word) {
return marked_for_removal.count(word) != 0;
}
), result.end());
 
return result;
}
 
// Return a set containing all of the shortest common superstrings of the given list of strings.
std::unordered_set<std::string> shortest_common_superstrings(const std::vector<std::string>& list) {
std::vector<std::string> deduplicated = deduplicate(list);
 
std::unordered_set<std::string> shortest;
shortest.emplace(std::reduce(list.begin(), list.end(), std::string("")));
 
uint64_t shortest_length;
for ( const std::string& word : list ) {
shortest_length += word.length();
}
 
for ( std::vector<std::string> permutation : permutations(deduplicated) ) {
std::string candidate;
for ( const std::string& word : permutation ) {
candidate = concatenate(candidate, word);
}
 
if ( candidate.length() < shortest_length ) {
shortest.clear();
shortest.emplace(candidate);
shortest_length = candidate.length();
} else if ( candidate.length() == shortest_length ) {
shortest.emplace(candidate);
}
}
return shortest;
}
 
int main() {
const std::vector<std::vector<std::string>> test_sequences = {
{ "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 ( const std::vector<std::string>& test : test_sequences ) {
for ( const std::string& superstring : shortest_common_superstrings(test) ) {
print_report(superstring);
}
}
}
</syntaxhighlight>
<pre>
Nucleotide counts for: TAGAAG
Bases: A 3, C: 0, G: 2, T: 1, total: 6
 
Nucleotide counts for: TAAGAA
Bases: A 4, C: 0, G: 1, T: 1, total: 6
 
Nucleotide counts for: GAAGTA
Bases: A 3, C: 0, G: 2, T: 1, total: 6
 
Nucleotide counts for: CATTAGGG
Bases: A 2, C: 1, G: 3, T: 2, total: 8
 
Nucleotide counts for: AAGAUGGAGCGCAUCGCAAUAAGGA
Bases: A 10, C: 4, G: 8, T: 0, total: 25
 
Nucleotide counts for:
CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA
Bases: A 74, C: 57, G: 75, T: 94, total: 300
</pre>
 
=={{header|Go}}==
{{trans|Julia}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 227 ⟶ 517:
printCounts(scs)
}
}</langsyntaxhighlight>
 
{{out}}
Line 270 ⟶ 560:
____________________
Total length 300
</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
 
public final class BioinformaticsGlobalAlignment {
 
public static void main(String[] aArgs) {
List<List<String>> testSequences = Arrays.asList(
Arrays.asList( "TA", "AAG", "TA", "GAA", "TA" ),
Arrays.asList( "CATTAGGG", "ATTAG", "GGG", "TA" ),
Arrays.asList( "AAGAUGGA", "GGAGCGCAUC", "AUCGCAAUAAGGA" ),
Arrays.asList( "ATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTAT",
"GGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGT",
"CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA",
"TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC",
"AACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTT",
"GCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTC",
"CGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCT",
"TGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC",
"CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGC",
"GATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATT",
"TTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC",
"CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA",
"TCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGA" )
);
for ( List<String> test : testSequences ) {
for ( String superstring : shortestCommonSuperstrings(test) ) {
printReport(superstring);
}
}
}
// Return a set containing all of the shortest common superstrings of the given list of strings.
private static Set<String> shortestCommonSuperstrings(List<String> aList) {
List<String> deduplicated = deduplicate(aList);
Set<String> shortest = new HashSet<String>();
shortest.add(String.join("", deduplicated));
int shortestLength = aList.stream().mapToInt( s -> s.length() ).sum();
for ( List<String> permutation : permutations(deduplicated) ) {
String candidate = permutation.stream().reduce("", (a, b) -> concatenate(a, b) );
if ( candidate.length() < shortestLength ) {
shortest.clear();
shortest.add(candidate);
shortestLength = candidate.length();
} else if ( candidate.length() == shortestLength ) {
shortest.add(candidate);
}
}
return shortest;
}
 
// Remove duplicate strings and strings which are substrings of other strings in the given list.
private static List<String> deduplicate(List<String> aList) {
List<String> unique = aList.stream().distinct().collect(Collectors.toList());
List<String> result = new ArrayList<String>(unique);
List<String> markedForRemoval = new ArrayList<String>();
for ( String testWord : result ) {
for ( String word : unique ) {
if ( ! word.equals(testWord) && word.contains(testWord) ) {
markedForRemoval.add(testWord);
}
}
}
result.removeAll(markedForRemoval);
return result;
}
// Return aBefore concatenated with aAfter, removing the longest suffix of aBefore that matches a prefix of aAfter.
private static String concatenate(String aBefore, String aAfter) {
for ( int i = 0; i < aBefore.length(); i++ ) {
if ( aAfter.startsWith(aBefore.substring(i, aBefore.length())) ) {
return aBefore.substring(0, i) + aAfter;
}
}
return aBefore + aAfter;
}
// Return all permutations of the given list of strings.
private static List<List<String>> permutations(List<String> aList) {
int[] indexes = new int[aList.size()];
List<List<String>> result = new ArrayList<List<String>>();
result.add( new ArrayList<String>(aList) );
int i = 0;
while ( i < aList.size() ) {
if ( indexes[i] < i ) {
final int j = ( i % 2 == 0 ) ? 0 : indexes[i];
String temp = aList.get(j);
aList.set(j, aList.get(i));
aList.set(i, temp);
result.add( new ArrayList<String>(aList) );
indexes[i]++;
i = 0;
} else {
indexes[i] = 0;
i += 1;
}
}
return result;
}
// Print a report of the given string to the standard output device.
private static void printReport(String aText) {
char[] nucleotides = new char[] {'A', 'C', 'G', 'T' };
Map<Character, Integer> bases = new HashMap<Character, Integer>();
for ( char base : nucleotides ) {
bases.put(base, 0);
}
for ( char ch : aText.toCharArray() ) {
bases.merge(ch, 1, Integer::sum);
}
final int total = bases.values().stream().reduce(0, Integer::sum);
System.out.print("Nucleotide counts for: " + ( ( aText.length() > 50 ) ? System.lineSeparator() : "") );
System.out.println(aText);
System.out.print(String.format("%s%d%s%d%s%d%s%d",
"Bases: A: ", bases.get('A'), ", C: ", bases.get('C'), ", G: ", bases.get('G'), ", T: ", bases.get('T')));
System.out.println(", total: " + total + System.lineSeparator());
}
 
}
</syntaxhighlight>
{{ out }}
<pre>
Nucleotide counts for: TAGAAG
Bases: A: 3, C: 0, G: 2, T: 1, total: 6
 
Nucleotide counts for: GAAGTA
Bases: A: 3, C: 0, G: 2, T: 1, total: 6
 
Nucleotide counts for: TAAGAA
Bases: A: 4, C: 0, G: 1, T: 1, total: 6
 
Nucleotide counts for: CATTAGGG
Bases: A: 2, C: 1, G: 3, T: 2, total: 8
 
Nucleotide counts for: AAGAUGGAGCGCAUCGCAAUAAGGA
Bases: A: 10, C: 4, G: 8, T: 0, total: 25
 
Nucleotide counts for:
CGTAAAAAATTACAACGTCCTTTGGCTATCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGTCTTGTTTCGAGAGTAACGGCTACCGTCTTCGATTCTGCTTATAACACTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA
Bases: A: 74, C: 57, G: 75, T: 94, total: 300
</pre>
 
Line 275 ⟶ 719:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq">
<lang jq>
### Generic helper functions
 
Line 287 ⟶ 731:
range(0;length) as $i
| [.[$i]] + (del(.[$i])|permutations)
end ;</langsyntaxhighlight><syntaxhighlight lang ="jq">
# Give a synoptic view of the input string,
# highlighting the occurrence of ACGTU letters
Line 320 ⟶ 764:
end);
 
# Given an array of deduplicated strings, attempt to find a superstring composed
# composed of these strings in the same order;
# return it if found, else null.
def relevant($min):
. as $in
| reduce range(0; length-1) as $i (.[0];length
| {s: .[0], if .i:0}
| until (.s == null or .i >= $length - 1;
then overlap_info(.; $in[$i+1]; $min) as $overlap
.i as $i
| if $overlap then (. + $in[$i+1][$overlap.overlap|length:])
# Since the strings have been deduplicated we can use $in[$i]:
else null
| overlap_info($in[$i]; $in[$i+1]; $min) as $overlap
| if $overlap then .s += $in[$i+1][$overlap.overlap|length:]
else .s = null
end
else| .i end)+= ;1 )
| .s ;
# Input: an array of strings
Line 343 ⟶ 791:
else . end)
| .shortestsuper;
</syntaxhighlight>
</lang>
'''The specific tasks'''
<syntaxhighlight lang="jq">
<lang jq>
def task1examples:
[
["TA", "AAG", "TA", "GAA", "TA"];
["TA", "AAG", "TA", "GAA", "TA"],
 
["CATTAGGG", "ATTAG", "GGG", "TA"],
def task2:
["CATTAGGG", "ATTAG", "GGG", "TA"];
 
["AAGAUGGA", "GGAGCGCAUC", "AUCGCAAUAAGGA"],
def task3:
["AAGAUGGA", "GGAGCGCAUC", "AUCGCAAUAAGGA"];
 
def task4:
["ATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTAT",
"GGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATCGAACGCAATAAGGATCATTTGATGGGACGTTTCGTCGACAAAGT",
Line 368 ⟶ 814:
"TTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGATGGAGCGCATC",
"CTATGTTCTTATGAAATGGATGTTCTGAGTTGGTCAGTCCCAATGTGCGGGGTTTCTTTTAGTACGTCGGGAGTGGTATTATA",
"TCTCTTAAACTCCTGCTAAATGCTCGTGCTTTCCAATTATGTAAGCGTTCCGAGACGGGGTGGTCGATTCTGAGGACAAAGGTCAAGA"];
];
 
def tasks:
def t: shortest_common_superstring | synopsis;
"Task 1:", (task1|t),
"\nTask 2:", (task2|t),
"\nTask 3:", (task3|t),
"\nTask 4:", (task4|t);
 
examples
tasks</lang>
| . as $examples
| range(0;length) as $i
| "Task \($i+1):", ($examples[$i]|t), "";
 
tasks</syntaxhighlight>
{{out}}
<pre>
Line 424 ⟶ 872:
Σ: 300
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Combinatorics
 
""" Given a DNA sequence, report the sequence, length and base counts"""
Line 507 ⟶ 954:
printcounts(scs)
end
</langsyntaxhighlight>{{out}}
<pre>
Nucleotide counts for TAAGAA:
Line 549 ⟶ 996:
Total length 300
</pre>
 
=={{header|Nim}}==
{{trans|Wren}}
<langsyntaxhighlight Nimlang="nim">import algorithm, sequtils, strformat, strutils, tables
 
const ACGT = ['A', 'C', 'G', 'T'] # Four DNA bases.
Line 633 ⟶ 1,079:
for test in TestSequences:
let scs = test.shortestCommonSuperstring
scs.printCounts()</langsyntaxhighlight>
 
{{out}}
Line 675 ⟶ 1,121:
————————————————————
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.
<syntaxhighlight 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.
</syntaxhighlight>
{{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}}==
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/Bioinformatics/global_alignment
Line 760 ⟶ 1,522:
use Data::Dump 'dd'; dd \%ch;
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 775 ⟶ 1,537:
{ A => 74, C => 57, G => 75, T => 94 }
</pre>
 
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">procedure</span> <span style="color: #000000;">printcounts</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">ss</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Given DNA sequence(s), report the sequence, length and base counts</span>
Line 863 ⟶ 1,623:
<span style="color: #0000FF;">}</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">shortest_common_superstring</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
(Shows three length-6 results for the first test)
Line 890 ⟶ 1,650:
Base counts: Other:0, A:74, C:57, G:75, T:94, total:300
</pre>
 
=={{header|Python}}==
{{trans|Go}}
 
<langsyntaxhighlight lang="python">import os
 
from collections import Counter
Line 1,010 ⟶ 1,769:
#
# .. if you don't want all possible shortest superstrings.
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,074 ⟶ 1,833:
Total length 300
</pre>
 
=={{header|Raku}}==
{{trans|Go}}
{{trans|Julia}}
<syntaxhighlight lang="raku" perl6line># 20210209 Raku programming solution
 
sub printCounts(\seq) {
Line 1,134 ⟶ 1,892:
>,
)
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,151 ⟶ 1,909:
(C 57 G 75 A 74 T 94) and total length = 300
</pre>
 
=={{header|Wren}}==
{{trans|Julia}}
Line 1,158 ⟶ 1,915:
{{libheader|Wren-str}}
{{libheader|Wren-math}}
<langsyntaxhighlight ecmascriptlang="wren">import "./fmt" for Fmt
import "./seq" for Lst
import "./str" for Str
import "./math" for Int
 
/* Gets all permutations of a list of strings. */
Line 1,276 ⟶ 2,033:
var scs = shortestCommonSuperstring.call(test)
printCounts.call(scs)
}</langsyntaxhighlight>
 
{{out}}
PureFox
9,477

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/307698...354543"