Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

Aufgabe Structs zur Datengruppierung

In der Biologie kann man Bakterien unter anderem daran identifizieren, welche Antibiotika gegen Sie wirksam sind und welche nicht (siehe auch https://de.wikipedia.org/wiki/Antibiogramm). Dazu sammelt man im Voraus die Reaktionen vieler bereits bekannter Bakterien auf mehrere Antibiotika und speichert diese in einer Datenbank. Will man jetzt ein unbekanntes Bakterium identifizieren, so testet man dessen Reaktion auf dieselben Antibiotika und sucht dann in seiner Datenbank nach Bakterien mit gleichen Eigenschaften.

In dieser Aufgabe werden wir eine solche Datenbankabfrage nachimplementieren. Dazu wird eine synthetische, also nicht auf echten Messungen basierende, Datenbank als Textdatei vorgelegt.

Die Datei ist folgendermaßen aufgebaut:

• Die erste Zeile enthält eine einzelne Ganzzahl, die die Anzahl der folgenden Zeilen angibt.
• Jede Zeile danach enthält eine eindeutige Identifikationsnummer, eine Zeichenkette für den Namen des Bakteriums und 30 Zahlen mit Werten 0 oder 1, die die Reaktion auf die einzelnen Antibiotika beschreiben, jeweils durch Leerzeichen getrennt. Eine 0 bedeutet "das Antibiotikum wirkt nicht", eine 1 bedeutet "das Antibiotikum wirkt".
  
  Die ersten 10 Zeilen der Datenbank sehen etwa so aus:

  1000000
  6069329 Gary000001 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0
  8664926 Larry000001 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0
  4211696 Sherry000001 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0
  3714429 Larry000002 0 1 0 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 1
  3534463 Larry000003 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 1
  3834709 Harry000001 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0
  1895957 Sherry000002 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1
  2050729 Cary000001 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
  3949739 Terry000001 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
  

Um diese Werte sinnvoll zu repräsentieren, verwenden wir folgende zwei structs.

struct antibiotic_sensitivities {
    bool sensitivity[30];
};

struct bacterium {
    uint64_t id;
    std::string name;
    antibiotic_sensitivities sensitivities;
};

Aufgaben Denken Sie daran, dass Argumente in C++ bei der Übergabe standardmäßig kopiert werden. Verwenden Sie Referenzen, um dies zu verhindern.

1. Schreiben Sie eine Funktion print_bacterium, die eine Instanz von bacterium nimmt und diese lesbar auf der Konsole ausgibt.
2. Schreiben Sie eine Funktion read_database, die die Textdatei einliest und einen https://en.cppreference.com/w/cpp/container/vector mit den eingelesenen Bakterien zurückgibt. Sie können hier zusätzlich eine Hilfsfunktion schreiben, die eine einzelne Zeile aus der Datei einliest und ein einzelnes bacterium zurückgibt.
3. Schreiben Sie eine Funktion print_database, die einen std::vector<bacterium> nimmt und jedes Bakterium mithilfe von print_bacterium auf der Konsole ausgibt.
4. Wir brauchen noch ein Ähnlichkeitsmaß bzw. Distanzmaß für Bakterien. Schreiben Sie eine Funktion distance, die zwei Objekte vom Typ antibiotic_sensitivities nimmt und zurückgibt, bei wie vielen Antibiotika sich die Reaktion auf das jeweilige Antibiotikum zwischen den Bakterien unterscheidet, d.h. an wievielen Stellen die Einträge im Array nicht paarweise übereinstimmen.
5. Schreiben Sie eine Funktion namens find_closest, die einen std::vector<bacterium> und ein einzelnes Objekt s vom Typ antibiotic_sensitivities als Argument nimmt und das Bakterium zurückgibt, das s gemäß des zuvor definierten Distanzmaßes am ähnlichsten ist. (Kürzere Distanzen sind besser!)
6. Ihnen liegen die folgenden drei bisher unbekannten Messungen für sensitivity vor. Finden Sie für alle drei Messungen mithilfe Ihrer vorher implementierten Methoden ein bekanntes Bakterium mit der kürzesten Distanz zur jeweiligen Messung. Es reicht, wenn Sie die Identifikationsnummer des gefundenen Bakteriums aufschreiben.

   0 0 1 0 1 1 1 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1
   0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 0 0
   0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1
   

7. Bonus: Für ein unbekanntes Bakterium wurden nicht alle Tests durchgeführt. Sie wissen nur, dass Antibiotika 0, 10, 12, 15 wirken und Antibiotika 7, 14, 29 nicht wirken. Sie könnten jetzt die Datenbank nach Bakterien filtern, die dieselbe Reaktion zeigen, aber das wären immer noch zu viele Ergebnisse. Sie überlegen stattdessen, weitere Tests mit anderen Antibiotika durchzuführen. Es kann hierbei passieren, dass alle noch möglichen Bakterien auf ein bestimmtes Antibiotikum gleich reagieren, was den Test mit diesem Antibiotikum sinnlos machen würde. Finden Sie die Nummern aller Antibiotika, auf die das zutrifft, d.h. alle Antibiotika, die gegen alle verbleibenden Bakterien wirken bzw. gegen alle verbleibenden Bakterien nicht wirken.

Beispiele für Arrays und Datei-Eingabe und -Ausgabe:

#include <fstream>
#include <iostream>

int main() {
    std::ofstream myfile("data.txt");

    int a = 42;
    int b = 7;
    int c = 789;
    int d = 8;
    myfile << a << " " << b << std::endl;
    myfile << c << " " << d;

    return 0;
}

#include <fstream>
#include <iostream>


int main() {
    std::ifstream myfile("data.txt");

    int a, b, c, d;
    myfile >> a >> b >> c;
    myfile >> d;

    std::cout << a << " " << b << " " << c << " " << d;

    return 0;
}

int main() {

    // 5 uninitialisierte double-Werte
    double s[5];

    // initialisiertes Array der Länge 3
    double s[] = {1.2, 1.6, -2.4};

    // struct-Werte können der Reihe nach initialisiert werden
    antibiotic_sensitivities as = {
        // das hier ist das sensitivity-Array
        {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}
    };

    // auf einzelne Elemente kann mit eckigen Klammern zugegriffen werden
    s[1] = 2 * s[0];
}