Misja

Jak dobrze wiadomo, materiał genetyczny wszystkich znanych stworzeń na Ziemi jest zakodowany w DNA; z użyciem czterech nukleotydów adeniny, tyminy, cytozyny i guaniny. (Zwykle reprezentowany przez ATGC).

Bioinformatyk pragnący przechowywać cały genom nie chciałby oczywiście przechowywać go jako ASCII, ponieważ każdy wybór może być reprezentowany przez zaledwie dwa bity!

Specyfikacja

Twoim zadaniem, jeśli zdecydujesz się to zaakceptować, jest napisanie pary programów, funkcji lub metod do konwersji reprezentacji ASCII na reprezentację binarną iz powrotem; reprezentujące Ajako b00, Tjako b01, Gjako b10i Cjako b11(odtąd „jednostki”).

Ponadto wysokie bity każdego bajtu powinny zawierać liczbę jednostek w bajcie, dzięki czemu każdy bajt reprezentuje tryplet.

Na przykład: "GATTACCA"staje się b11 100001 b11 010011 b10 1100xx.

W ASCII na dane binarne spacje, tabulatory i znaki nowej linii powinny być ignorowane. Każdy znak spoza zestawu [ \r\n\tATGC]jest błędem i może zostać zignorowany lub przerwać przetwarzanie.

Na wejściu binarnym do ASCII bajty, których dwa wysokie bity są b00zignorowane.

Dane wyjściowe ASCII mogą zawierać białe znaki; ale nigdy nie powinien przekraczać czterokrotnie wielkości wejścia binarnego plus jeden bajt i musi kończyć się nową linią.

Wyjście binarne może zawierać dowolną liczbę b00xxxxxxbajtów „kontrolnych”; ale nigdy nie może być dłuższy niż wejście ASCII.

Każdy program konwersji musi obsługiwać wprowadzanie dowolnej długości; i powinien zakończyć kodowanie lub dekodowanie w przybliżeniu w czasie liniowym.

Zwrot akcji

Na nieszczęście dla bioinformatyka, dla którego wykonujesz to zadanie, w jakiś sposób cię skrzywdził, na osobistym, ale być może drobnym poziomie.

Być może kiedyś wyszedł z twoją siostrą i nigdy więcej do niej nie dzwonił. Być może nadepnął na ogon twojego psa. Specyfika nie jest tak naprawdę ważna.

Ważne jest to, że masz szansę na zwrot!

Szczegóły

Każda konwersja powinna wprowadzać niewielki poziom błędu; rzędu jednego błędu na dziesięć tysięcy do miliona przetworzonych jednostek.

Błąd może być jednym z następujących:

• Błędy powielania: "GAT TAC CA"stają się"GAT TAA CCA"
• Błędy usuwania: "GAT TAC CA"stają się"GAT TAC A"
• Błędy w tłumaczeniu: "GAT TAC CA"stają się"GTA TAC CA"
• Duplikacje trojaczne: "GAT TAC CA"stają się"GAT TAC TAC CA"
• Poślizgnięcia trojaczki: "GAT TAC CA"stają się"TAC GAT CA"
• Odwrócenie trojaczki: "GAT TAC CA"staje się"GAT CAT CA"

Błędy zostaną wprowadzone, oczywiście nie powinny być od razu oczywiste z kodu; i niezależnie od długości wkładu; konwersja powinna wprowadzić co najmniej jeden błąd.

Dwa przebiegi z identycznymi wejściami niekoniecznie powinny dawać identyczne wyniki.

Sztuczka

Podły bioinformatyk jest umiarkowanie kompetentnym programistą; i jako takie niektóre konstrukcje zostaną automatycznie wykryte i jako takie zostaną zablokowane:

• Automatycznie wykryje wszystkie wywołania systemowych generatorów liczb losowych, takich jak rand (), random (), lub czytanie z / dev / urandom lub / dev / random (lub dowolnego innego odpowiednika językowego).
• Zauważy również wszelkie zbędne zmienne, liczniki lub pętle.

Punktacja

Enkoder i dekoder będą oceniane indywidualnie.

Każdy będzie uruchamiany 3 razy na zestawie 100 losowo generowanych plików wejściowych, każdy o rozmiarze rzędu 3 milionów jednostek.

Dane dla przypadków testowych enkodera zostaną utworzone mniej więcej tak:

for (l = 1 => bigNum)
  for (t = 1 => 20)
    random_pick(3,ATGC)
    t == 20 ? newline : space

Dane dla przypadków testowych dekodera zostaną utworzone mniej więcej tak:

for (u = 1 => bigNum)
  for (t = 1 => 20)
    random_byte() | 0b11000000
   0x00

Enkoder

• Każdy brakujący bajt w oczekiwanej minimalnej długości w rzeczywistej długości uzyska -1 punkty, maksymalnie do -1000. (Oczekiwana minimalna długość to ceil(count(ATGC) / 3).)

Dekoder

• Każdy bajt powyżej oczekiwanej maksymalnej długości rzeczywistej długości uzyska -1 punkty, maksymalnie do -1000. (Oczekiwana maksymalna długość to size(input) * 4 + 1.)

Obie

• Każdy rodzaj błędu, który może zostać popełniony, zdobędzie 100 punktów; za łącznie 600 punktów możliwych na każdy, 1200 łącznie.
• Każdy przypadek testowy, w którym enkoder generuje ponad 30% więcej lub mniej błędów niż jego średnia, będzie karany o -5 punktów.
• Każdy przypadek testowy, w którym enkoder generuje mniej niż 15% więcej lub mniej błędów niż jego średnia, otrzyma 5 punktów.
• Każdy przypadek testowy, w którym wszystkie trzy przebiegi dają identyczne wyniki, będzie karany o -10 punktów.

Trudne wymagania

Zgłoszenie zostanie zdyskwalifikowane, jeżeli:

• Dla każdego ważnego wejścia dłuższego niż jeden triplet nie generuje nawet jednego błędu.
• Jego działanie jest takie, że nie może ukończyć testowej rękawicy w ciągu około godziny.
• Średnio wytwarza więcej niż jeden błąd na każde dziesięć tysięcy jednostek.
• Średnio wytwarza mniej niż jeden błąd na każdy milion jednostek.

Interfejs

Uczestnicy powinni zaakceptować dane wejściowe na standardowe dane wejściowe i dane wyjściowe na standardowe dane wyjściowe.

Jeśli pozycja dotyczy jednego programu z podwójną funkcją; przełączniki -ei -dpowinny ustawić program odpowiednio do kodowania i dekodowania.

Przykładowe inwokacje:

$ encoder <infile.txt >outfile.bin
$ decoder <infile.bin >outfile.txt
$ recoder -e <infile.txt >outfile.bin

Zwycięzca

Zwycięzcą jest zgłoszenie o najwyższym wyniku; teoretyczne maksimum wynosi 1200 dla rodzajów błędów plus 3000 punktów za stabilność wskaźnika generowania błędów.

W mało prawdopodobnym przypadku remisu; zwycięzca zostanie określony na podstawie liczby głosów.

Dodatkowe uwagi

Do celów uruchomienia rękawicy testowej każdy wpis powinien zawierać instrukcje uruchamiania lub kompilacji.

Najlepiej, jeśli wszystkie wpisy powinny być uruchamiane na komputerze z systemem Linux bez X.

Perl 5.10

Z przyjemnością przedstawiam moje rozwiązanie w Perlu.

Kiedy rozpocząłem wyzwanie, byłem całkiem pewien, że Perl pozostanie znacznie poniżej limitu 1 godziny.

Do celów testowych opracowałem prosty generator próbek i generator kodowanych próbek.

Potem opracowałem koder, który wymagał większego wysiłku i stworzył dłuższy kod. Koder działa w następujący sposób:

1. Pierwsza pętla odczytuje cały plik i dzieli dane, aby uzyskać tablicę wszystkich trojetów
2. druga pętla przechodzi przez tablicę i dodaje do każdego elementu jej długość
3. trzecia pętla przechodzi ponownie i odwzorowuje każdy znak, dając wynik.

Zakodowane wyjście binarne jest sformatowane jako „linia” zakończona nowym wierszem zawierająca 20 oktetów, gdzie każdy oktet koduje jedną triplet, z dwoma znakami prefiksu (jak cykliczny numer linii).

na przykład najkrótsze trzy bajtowe dane wejściowe:

AAA

powinien dać najkrótszy wynik z trzech bajtów plus znak nowej linii.

00ÿ

to jest

30 30 FF 0A

i

AGG CGC AAC GGC TAA ATC GTT TTC ACA CCA CGT TTG AAA CGG GTG ACA CGA GAT TTA GTC
TAT GGT ACT AGG TAC GCC GTG GTG CGT GCG GAG TTA CTA GAT GTG TTA GTA CGC CAT CGT

powinien dać następujący plik binarny.

01ÊûÃëÐÇå×ÌüùÖÀúæÌøáÔç
00ÑéÍÊÓïææùîâÔôáæÔäûñù

Powinien z powodu małego wskaźnika błędów: w przypadku najmniejszych danych wejściowych skrypt wprowadza 1 błąd.

W przypadku uruchomienia 3 milionów plików trojaków enkoder wprowadza 11 błędów.

Pod warunkiem, że skrypt to dnacodec3.pl, uruchomienie jest uruchamiane w wierszu polecenia jak zwykle:

$> perl dnacodec3.pl -e < plain.txt > coded.txt

Dekoder działa w następujący sposób:

1. Pierwsza pętla odczytuje cały plik i dzieli dane, aby uzyskać tablicę wszystkich oktetów. Śledzi każdą nową linię.
2. druga pętla sprawdza każdy oktet, zachowując te, które nie zaczynają się od 00, i pomija resztę. Zwykły wynik Ascii jest sformatowany jako zakończone nowym wierszem wiersze trojaczków oddzielone jedną spacją. Nowa linia znajduje się w tej samej pozycji, co na wejściu.

Przygotowałem próbny plik testowy z 3 milionami trojetów (około 12 MB) i przetestowałem pod kątem czasu. Używając mojego laptopa z procesorem Intel Core i5 vPro o częstotliwości 2,6 GHz, praca kodera 3M zawsze zajmuje mniej niż 20 sekund. Podczas biegu zajmuje 200-220 MB pamięci RAM. Co za strata!

Przebieg dekodowania zajmuje mniej niż 10 sekund. Nie może wprowadzić błędów ... na razie.

Ponownie, do uruchomienia dekodowania

$> perl dnacodec3.pl -d < coded.txt > plain.txt

Oto kod

#!/usr/bin/perl
use strict ;
use warnings ;
my $switch = shift || die "usage $0 [-e|-d]\n";
my %map = qw( x 10  X 11  c 0b  ? 00
              A 00  T 01  G 10  C 11  
              0 00  1 01  2 10  3 11  
              00 A  01 T  10 G  11 C  ) ;
my $r = 20 ;
my @dummy = unpack ( '(A4)*', '0xxx' x $r ) ;
my $map = oct( $map{ c } . ($map{ C } x 9) ) ;
my $t = time() ;
my @inp = () ;
my @out = () ;
my @buf = () ;
my $n ;

sub arch {
    push @buf, @dummy[ 0 .. $r - $#buf - 2 ] ;
    push @out, "@buf" ;
    @buf = () ;
}

sub encode {
    my $mask = '(A3)*' ;
    while ( my $row = <STDIN> ) {
        chomp $row ;
        $row =~ s/\s+//g ;
        $row =~ s/[^\r\n\tATGC]//g ;
        next unless $row ;
        my @row = unpack( $mask, $row ) ;
        push @inp, @row if $row ;
    }
    $n = scalar @inp ;
    $r = $n if $r > $n ;
    for ( my $i = $n - 1 ; $i >= 0 ; --$i ) {
        my $e = $inp[$n-$i-1] ;
        my $l = length( $e ) ;
        my $d = $e =~ /\?/? 0: $l ;
        push @buf, ( $d -((($i-($n>>1))&$map)?0:1) )
           . $e . 'x'x(3-$l) ;
        arch unless $i % $r ;
    }
    arch if scalar @buf ;
    my $m = scalar @out ;
    for ( my $j = $m - 1 ; $j >= 0; --$j ) {
        my @ary = () ;
        my $e = $out[$m-$j-1] ;
        for my $byte ( split / /, $e ) {
            my @byte = split ( //, $byte ) ;
            my @trad = map { $map{ $_ } } @byte ;
            my $byte = join( '', @trad ) ;
            push @ary, $byte ;
        };
        my $row = sprintf( '%02d', $j % $r) ;
        $row .= pack( '(B8)*', @ary ) ;
        print "$row\n" ;
    }
}

sub decode {
    my $mask = '(B8)*' ;
    while ( my $row = <STDIN> ) {
        chomp $row ;
        next unless $row ;
        my @row = unpack( $mask, $row ) ;
        push @inp, @row[0..$#row], '?' if $row ;
    }
    $n = scalar @inp ;
    my @ary = () ;
    for ( my $i = $n - 1 ; $i >= 0 ; --$i ) {
        my $e = $inp[$n-$i-1] ;
        if ( $e ne '?' ) {
            my $u = oct( '0b'. substr($e,0,2) ) ;
            my $a = '' ;
            for my $j ( 1 .. $u ) {
                $a .= $map{ substr($e,$j+$j,2) } ;
            }
            push @ary, $a if $u ;
        }
        else {
            my $row = "@ary" ;
            $row =~ s/\s{2,}//g ;
            print "$row\n" if $row ;
            @ary =() ;
        }
    }
}

decode if $switch eq '-d' ;
encode if $switch eq '-e' ;

A oto przykładowy generator:

sub test_coder {
    my $n = shift || 1000 ;
    my @b = qw( A C G T ) ;
    for (my $l = 0; $l < $n; $l++) {
        my @ary = () ;
        for (my $t = 0; $t < 20; $t++) {
            push @ary, $b[ int(rand(4)) ] . $b[ int(rand(4)) ] . $b[ int(rand(4)) ] ;
        }
        print "@ary\n" ;
    }
    1;
}

sub test_decoder {
    my $n = shift || 1000;
    for (my $l = 0; $l < $n; $l++) {
        my @ary = () ;
        for (my $t = 0; $t < 20; $t++) {
            push @ary, int(rand(256)) | 0b11000000 ;
        }
        my $row = pack( 'C*', @ary ) ;
        print "$row\000" ;
    }
    1;
}


test_coder( @ARGV ) if $switch eq '-g' ;
test_decoder( @ARGV )  if $switch eq '-h' ;