Arduino as a MIDI/Bluetooth Relay for Windows 8.1 Apps

In my last post I described how a Bluetooth connection between Arduino and a Windows 8.1 device can be established.

The next step for me was to connect the Arduino to my electronic drum kit which has both, a MIDI-IN and a MIDI-OUT jack, but any other electronical instrument will do as well.

The wiring diagram for an Arduino Uno R3 with MIDI-IN/OUT and the JY-MCU Bluetooth module is shown in Fig.1. NOTE: Occasionally there are MIDI shields available for Arduino, so you might not have to build it on your own.

Fig.1: You'll need a few resistors, a diod, an optocoupler and preferably one or two DIN-jacks

Fig.1: You’ll need a few resistors, a diod, an optocoupler and preferably one or two DIN-jacks

The Arduino code to relay MIDI>Bluetooth and Bluetooth>MIDI is actually quite simple.

//by Michael Osthege (2013)
#include "SoftwareSerial.h"
const int TX_BT = 10;
const int RX_BT = 11;
const int MIDI_TX = 1;
const int MIDI_RX = 0;
//======================================================bluetooth setup
SoftwareSerial btSerial(TX_BT, RX_BT);
void setup()
    Serial.println("Bluetooth initialized");
//======================================================do work
void loop()
    ReadMIDI();//listen on the MIDI-IN
    ReadBluetooth();//listen for Bluetooth
void ReadMIDI()
    if (Serial.available() > 0)//there's something in the buffer
        char buffer[3];
        Serial.readBytes(buffer, 3);//receive it
        btSerial.write(buffer[0]);//relay it
void ReadBluetooth()
    if (btSerial.available() > 0)//there's something in the buffer
        char buffer[3];
        btSerial.readBytes(buffer, 3);//receive it
        Serial.write(buffer[0]);//relay it

As I understand it, the MIDI protocol communicates with commands of three bytes. Therefore I decided to relay all incoming serial messages in chunks of three bytes.

To test the relay, I modified the BluetoothConnectionManager of my previous example to send/receive chunks of 3 bytes as MIDI commands too. Incoming commands are printed into lines of text and simple sounds can be sent as well.

You can try it out yourself in this sample application:

Have a nice weekend =)

Bluetooth communication between Arduino and Windows 8.1


Recently, after being inspired by this video of Arduino Bluetooth communication with Windows Phone 8 by Marcos Pereira, I got myself some new devices to play with:

  • Arduino Uno R3 in a starter kit (link)
  • JY-MCU Bluetooth module (link)
  • and a few extra cables

The thing is: I don’t have a Windows Phone 8 yet and the Windows Phone 7.8 APIs do not support this kind of Bluetooth communication.

But: I have a Surface RT and with Windows 8.1 the RFCOMM API can be used to establish a serial link to the Arduino.

Arduino and Visual Studio

It happens that my developing skills are quite limited to C# and when I had to develop some Kinect software with Processing in early 2012, I almost freaked out. Arduino code is written in C++  and the standard Arduino IDE is derived from the Processing IDE. Fortunately there’s the Visual Studio extension VisualMicro which brings a very intuitive Arduino support for VS2010-VS2013. (not available for Express versions)

You can get VisualMicro for free at They also offer a pro-version (>$20) with support for Breakpoint-Debugging.

The Arduino IDE should be installed as well and you have to tell the VisualMicro extension where to find it.

Setting up the Arduino board

For the setup I’ll show here, I set up two LEDs, a potentiometer and of course the Bluetooth module (Fig.1).

Arduino UNO R3 with 2 LEDs, a potentiometer and a Bluetooth module

Fig.1: Arduino UNO R3 with 2 LEDs, a potentiometer and a Bluetooth module

Preparing the Code

The Arduino has to be loaded with some code to send and receive Bluetooth messages. I created a Visual Studio solution with a blank Windows 8.1 app and a new Arduino sketch and added a new header file “SoftwareSerial.h” (Fig.2). The code of SoftwareSerial.h can be found here.

A blank VS 2013 solution was created to which a blank Windows Store 8.1 application and an Arduino sketch were added.

Fig.2: A blank VS 2013 solution was created to which a blank Windows Store 8.1 application and an Arduino sketch were added.

The actual Arduino code can be studied in the sample application:

For the Windows 8.1 app we build a class, BluetoothConnectionManager to simplify enumerating, connecting, send & receive and state management. The code of the BluetoothConnectionManager and the actual application can also be studied in the sample application.

For the Windows 8.1 app it’s very important to declare the right Bluetooth capabilites. The following snippet should be included in Package.appxmanifest:

    <m2:DeviceCapability Name="bluetooth.rfcomm">
      <m2:Device Id="any">
        <m2:Function Type="name:serialPort" />

As soon as you have everything set up, the Arduino code can be deployed via Debug\Start new instance and the Windows 8.1 app can be launched.

In the sample application I implemented broadcast of the potentiometer value and switching the LEDs on/off. Additionally the red LED automatically turns on/off depending on the analog value.

One problem that this implementation brings, which I did not yet solve, is that simultaneous sending of a message by either party causes the other one to crash or get an exception. But due to my lack of experience, I do not know how to lock the streams to prevent this from happening..

Anyways, have fun =)

A Custom (Async) MessageBox for WPF and Windows Phone

The System.Windows.MessageBox provided by .NET is limited to a very small set of MessageBoxButtons (Yes/No/OK/Cancel) which do not allow for custom Button texts. The System.Windows.Forms.MessageBox also blocks the UI thread, which can be an annoying disadvantage as well.

The MessageBox on Windows Phone has the same disadvantages.

Custom buttons in a MessageBoxe simplify the decision for the user, because they can describe the results of the action:

Use your own buttons and await the result!

Use your own buttons and await the result!

This MessageBox does not block the UI thread!

This MessageBox does not block the UI thread!

However you need to do this with a custom control, so for WPF as well as Windows Phone I designed a simple method for asynchronously showing a MessageBox with custom buttons. (The WPF implementation based on this control by Evan Wondrasek)

So let’s bring some sample code.In WPF you can use multiple custom buttons:

asynchronously show a CustomMessageBox - int result is the number of the selected button, or the default

asynchronously show a CustomMessageBox – int result is the number of the selected button, or the default

And on Windows Phone you’re limited to 2 buttons:

asynchronously show a CustomMessageBox - int result is the number of the selected button, or the default

asynchronously show a CustomMessageBox – int result is the number of the selected button, or the default

To use CustomMessageBox, you need to get TCD.Controls from NuGet:

Install the TCD.Controls package from NuGet

Install the TCD.Controls package from NuGet

And on Windows Phone 7.x you also need async support, which is included in the Microsoft.Bcl.Async package:

Microsoft.Bcl.Async is required for async/await on WP7

Microsoft.Bcl.Async is required for async/await on WP7

Just like the other methods from TCD.Controls, CustomMessageBox also features IntelliSense descriptions (or I’ll add them very soon).

Please feel free to provide feedback and/or report bugs 😉

In-App Donations for Windows 8 Apps

Recently I wanted to offer my customers the opportunity to donate some money. No extra features, just a clean donation option.

In-app purchases seemed to be the best option. The idea is to have a list of products which have a price and contain “donate” in their product ID (Fig. 1).

Fig. 1: in-app products contain “donate” in their product name.

Fig. 1: in-app products contain “donate” in their product name.

In the app the list of products can be retrieved and shown when a donate button is tapped. If donations have been given can be checked by enumerating the existing licenses and looking for the “donate” term (Fig. 2).

Fig. 2: The buttons first indicates its activity and then shows the available in-app donation products.

Fig. 2: The buttons first indicates its activity and then shows the available in-app donation products.

Reasonably simple right? Well the principle is simple, but in-app purchases are a bit tricky to develop, debug and get through certification. (It took me 7 submissions to get it right..)

Those are the things that can result in certification failure:

  • no internet connection -> exception
  • store does not respond properly -> exception
  • error message looks to much like a error message -> fails requirement 3.2

The CurrentApp static class offers the methods to retrieve LicenseInformation and to execute purchases, but it won’t function until the app is actually released. Therefore you have to use the CurrentAppSimulator – conditionally depending on the build mode. For example:

return CurrentAppSimulator.LicenseInformation;
return CurrentApp.LicenseInformation;

Even in the certification environment, the store does not know your app, which results in an exception!

As you usually need to handle this, its common practice to show a MessageDialog informing the user what has gone wrong. The dialog should not look like a error message, but rather like a information, otherwise the tester might decide to let you fail said requirement 3.2!

As I want to offer in-app donations in multiple of my apps, I created a UserControl for it – the AppBar button you saw above.

I set up a code sample at MSDN, so you can take a look at the code there =)

DIY laser-shooting range

This is probably the first post on (hopefully) a series of ‘offtopic’ posts covering cool things I’ve done and consider worth sharing. It’s about a side project we did more than two years ago, while working on multitouch tables and IR technology.

At first we incorporated a 780 nm infrared laser into a plastic MP5 soft-air toy gun. The laser perfectly fit into the barrel (Fig. 1a). Two 1.5 V batteries were placed inside the hold (Fig. 1b) and wired with a 25 V/470 µF, a switch and the laser (Fig. 2).

Figure 1 – Inside of the modified MP5 softair, there’re battery pack (b), 470 µF capacitor and some mechanic to trigger the switch. The 780 nm laser (a) perfectly fits into the barrel.

Figure 1 – Inside of the modified MP5 softair, there’re battery pack (b), 470 µF capacitor and some mechanic to trigger the switch. The 780 nm laser (a) perfectly fits into the barrel.

Figure 2 - The circuit diagram for a pulsed laser.

Figure 2 – The circuit diagram for a pulsed laser.

The idea behind using a capacitor is to prevent continuous firing of the laser, most importantly as a security measure.

The assembled MP5 laser gun can then be used to fire light bursts of a few milliseconds.

To track the infrared light spots on a projection surface, we used a modified Hercules Classic Silver webcam. It’s a very cheap model (only 320×240 pixels) but it features a M12 lens with integrated IR filter which can easily replaced by a custom M12 lens with a bandpass filter, transparent for infrared light. Another reason we used the Hercules Classic Silver is that my grandpa had it laying around.

Community Core Vision (CCV) and MultiTouchVista (MTV) were used to create Windows touch input from the IR spots. (Note: On Windows 8 I’d recommend my TouchInjector software instead of MTV, as it’s more responsive and easier to set up.)

After calibration of the projection screen dimensions in CCV (using a single IR LED, or another (infrared) light source) we were able to shoot mouse clicks onto the screen with the laser MP5.

One might suggest to play the game Moorhuhn, but it should be noted that Moorhuhn spans across the screen and requires scrolling (at least if you want to shoot ’em all). For that reason I wrote the WPF application “LaserRange” (app & sources, requires .NET 4.5), that can be used to shoot blue circles of varying size. Precision, as well as reaction time get scored and, of course, there’s a lasergun sound effect 😉

2 months Surface RT – some thoughts from scientists perspective

There are countless reviews on the Surface RT already, but I consider myself some kind of non-average user, so I’d like to share my experience too.

To understand my argument on the device, you should know:

Who I am

I am a undergraduate Biology student from Germany with some experience in WPF/Multitouch/Kinect/Windows Phone/Windows 8 development using C#. Most software I write is just for personal use, but I published some of my work (WP7, Win8) as well. Since the launch of the first public beta, I‘ve been using and developing for the Windows 8 platform, so I have a reasonable understanding of what’s going on.

The Surface RT is my very first tablet computer. I’ve considered to get other devices (HP ElitePad, Samsung – ARM as well as x86), but decided that the Surface RT was the best fit.

Everyday tasks

Just like my HTC Mozart, I use the Surface a lot. It accompanies me to lectures, in the lab, or when travelling by train. Except for watching my favorite TV series, I don’t use it for entertainment (gaming, music), but for creating, or studying.


In a lecture I  take notes and or follow the slides and maybe sometimes even browse Reddit or Facebook. Before the Surface, I used to do this with my phone, usually causing the battery to be dead until 4 PM..

+ taking notes, following slides

+ less smartphone-battery drain

+ charge the phone in the lecture =D

– PDF editing (Reader, PDF Touch) apps need to be improved


I travel about 5 hours a week by train and use the Surface to watch my favorite TV series, or to go through lecture slides (aka study). To connect to the internet, I need to use my phones Internet Sharing, but I usually don’t do that, because A there’s almost no connectivity on the train and B due to my 50 MB data contract, it’s painfully slow. (Actually not significant for Twitter/FB/Mail on the phone.)

Sometimes I use the time on the train to write protocols, which involves a lot of Word and Excel. Equipped with a type cover, I can be productive without carrying something big and heavy.

In the Lab

As I mentioned, I‘m studying Biology, so we have a lot of internships/lab work where we do experiments and stuff. We need to write protocols on the experiments – that’s where Surface comes in. Taking measurements and pictures can be a lot of work (and chaotic) if you don’t have the right setup. For that purpose I wrote an app that can be used to manage the data, pictures, videos and files of many experiments while maintaining their context.

The data is not synced to the cloud or something (I’m just not that good..), but stored in either the app, or a folder you can select. In my case it’s a BitLocker-encrypted 16 GB USB key (you can see it in Figure 2 below) drive (8.50 €).

Figure 2: You can make a tree-like structure for your experiments and add fields of data, as well as files.

Figure 2: You can make a tree-like structure for your experiments and add fields of data, as well as files.

Figure 2: You can make a tree-like structure for your experiments and add fields of data, as well as files.

Figure 2: You can make a tree-like structure for your experiments and add fields of data, as well as files.

There are still many things I’d like to improve about the app, but I already use it heavily in the lab.

This is exactly the kind of use case where the Surface RT scores best, because of its long lasting battery, robustness, performance, weight and of course the USB port.

When taking a lot of measurements wich would usually be stored on paper, I can immediately type them into the Excel sheet instead.

The only disadvantage of Windows RT at this point may be that you can’t run the specialized software you usually work with as a scientist (device-specific control software, ImageJ, or other software you probably never even heard of). Technically Windows RT apps are perfectly capable of these things, but most of the time you’re using software which hasn’t been updated for many years, or even decades (no kidding, take a look at Figure 3!) and therefore won’t be ported anytime soon..

Figure 3: I have no idea how old this thing is, but it's frequently used!

Figure 3: I have no idea how old this thing is, but it’s frequently used!

With a Windows 8 Pro tablet one could analyze the data, but for capturing stuff the Surface RT is great and you can still use it as a real tablet as it does “connected standby”, the battery lasts longer etc.!

I love my Surface RT, use it a lot and can absolutely recommend it to anybody else. There are tons of things I didn’t mention and lots of RT apps to come =)

I’d also love to hear your thoughts on non-mainstream use cases^

Localizing Enums (in a ComboBox)

Enums have many useful applications and are often used in CoboBoxes to let the user select things. In the code behind the enum values are often defined using more or less cryptic text, because neither spaces, special characters, or leading numbers can be used in enum values (for good reasons!). Therefor it is necessary to change the text to something more understandable (language-localized in some cases).

One way to achieve this is to create the ComboBox items manually, but it’s much more comfortable to fill the ComboBox items directly with the enum values, because you can get/set the SelectedItem without converting it back and forth from/to the enum value.

You can’t override the .ToString() method of the Enum type, so we have to come up with another solution.

Just like any other control, the ComboBox uses a Template to create its items. We will replace the default template with one that uses a Comverter to populate the items.

The converter will be called “EnumNameConverter” and that’s its code:


As you can see the converter checks if the passed value is of type Enum, so if it’s ‘misused’ it will not throw an Exception. Then it calls an extension method ‘GetValueName’ that will care for converting the Enum to a string. (We could do this in the Converter as well, but if we do it in an extension method, you can use it independently of the Converter.)

That’s the code of the GetValueName extension method:


We have three options to convert the Enum value to a string:

  1. If the GetValueNameMethod was set to something (I’ll come back to that later)
  2. The System.ComponentModel.DataAnnotiations.Display Attribute (its Name property) can be used to describe an Enum’s value directly in the definition – the downside: it only allows for static values, thus no localization logic is available
  3. The inherited .ToString() method that would be used by the default template

If either of the methods returns a null/whitespace/empty string, we will fall back to the next one.

Now let’s talk about the GetValueNameMethod property. It’s a static property of the EnumExtensions class. You can set it to any method of type void(string) of your liking. And it just happens that if you implement resource localization like explained in the samples (keyword: x:Uid) you will have a GetString(string) method that returns the localized string from your resource file. To localize an Enum you need to add a new entry to your Resources.resw file:

Key: EnumName_EnumValueValue: LocalizedEnumValue

Key: EnumName_EnumValue
Value: LocalizedEnumValue

Now we can localize any Enum value to a string using the Enum.Value.GetValueName() method.

For the ComboBox to use the Converter, we need to define the new ItemTemplate. That’s the code:


To use the template from an extension method, a few tricks have to be used. I won’t go into the details, but you can contact me if you want to know^

For the TCD.Controls package, I wrote another extension method (to the ComboBox type) that applies this template for you. Just call .UseEnumItemTemplate() on the ComboBox you want to use with Enums.

Bottom line:

  • EnumExtensions.GetValueNameMethod
    • set this to your LocalizedStrings.GetString(string) method
  • Enum.Value.GetValueName
    • returns localized string, DisplayAttribute.Name, or .ToString
  • ComboBox.SetUpItems
    • fill the ComboBox with enum values (take a look at the overrides/parameters!)
  • ComboBox.UseEnumItemTemplate
    • prepare the ComboBox for the Enum items

I’ve uploaded a code sample to the MSDN sample gallery as well:

Keyboard Dismissing ComboBox

In the last few days I came across a design issue with the touch keyboard on Windows 8. The keyboard dismissal logic (documented here) defines a list of controls which do not cause the keyboard to dismiss when they get focused. The purpose is to prevent the keyboard from opening and closing all the time when the user fills out a form and is likely to switch between keyboard-editable controls such as TextBox and other controls like AppBar, Checkbox, RadioButtons the ComboBox and some more.

While that works fine with the other controls, ComboBox expands when interacted with and might get covered by the touch keyboard. And unfortunately you can’t change that behavior, or manually dismiss a deployed touch keyboard. (The user is in complete control over the keyboard.)

While on the MSDN forums it was suggested to alter the layout such that the ComboBox is less likely to collide with the touch keyboard, this was unacceptable in my case. (Screenshot below…)

Screenshot of my app, where I first met the problem

Screenshot of my app, where I first met the problem

I decided to go for a user control that encapsulates a real ComboBox, but intercepts the pointer, causing the keyboard to dismiss. This is done by setting IsHitTestVisible=false on the ComboBox and set it to true after the container (a Button control) was tapped (and caused the keyboard to dismiss). Because the ComboBox did not handle the tap, it need to be opened manually. You can of course control a ComboBox with the keyboard as well (arrow keys, space, enter, tab) and I had a few issues with that, but finally I got it right and now you can’t distinguish the KeyboardDismissingComboBox from a real one 😊

The KeyboardDismissingComboBox exposes the underlying ComboBox as a property so you can manually edit the items, subscribe to SelectionChanged or edit the template. However, you should not touch the IsHitTestVisible property, as this is vital to the dismissal behavior.

I for my part use ComboBoxes often to let the user select an enum value. For that reason I created an extension method (SetUpItems) to the ComboBox type which can be used to fill it with the values of an enum (first override) and optionally select the default item upon initialization (second override). The only limitation is that you can’t do that from XAML, but from Runtime only.

The control is now part of the TCD.Controls package on NuGet.

Please feel free to report bugs, or suggest changes 😉

03 Der Needleman-Wunsch-Algorithmus

  1. Einführung in die Bioinformatik
  2. Scoring von Alignments
  3. Der Needleman-Wunsch-Algorithmus

Die F-Matrix (abstrakt)

Der Needleman-Wunsch-Algorithmus geht bei der Berechnung des idealen Alignements in zwei Schritten vor, um exponentiell skalierende Rechenzeit zu vermeiden. Zunächst wird die sogenannte F-Matrix berechnet, aus welcher anschließend das ideale Alignment zusammengesetzt wird.

Zur Veranschaulichung alignen wir die Sequenzen GACFC und GCFHC.

Jedes Feld in der Matrix (jede Zelle der Tabelle) beinhaltet einen Score. Diese Punktzahl ist jene, die auf dem Weg zur Berechnung des Feldes gesammelt wurde. Zur Berechnung einer Zelle sind immer die Felder links oben, oben und links notwendig:

Unter den drei Feldern wird jenes gewählt, durch das sich die Höchste Punktzahl erreichen lässt:

  • Oben, wenn eine Lücke in der zweiten Sequenz (Spalten der Tabelle) die meisten Punkte bringt. Punktzahl = oberes Feld + gap penalty = -8 + -8 = -16
  • Oben-links, wenn das entsprechende Aminosäure-Paar die meisten Punkte bringt. Punktzahl = oben-links + Score(G-G) = 0 + 8 = 8
  • Links, wenn eine Lücke in der ersten Sequenz (Zeilen der Tabelle) die meisten Punkte bringt. Punktzahl = linkes Feld + gap Penalty = -8 + -8 = -16

Die höchste Punktzahl ist 8, also wird das Feld oben-links gewählt.

Wir gehen nun ein Feld nach rechts und berechnen wieder die möglichen Punktzahlen:

Die blauen Striche zeigen den Rechenweg, der gegangen wurde, um die Punktzahl eines Feldes zu berechnen. Horizontale und Vertikale Striche verwenden die gap Penalty. Beim diagonalen Rechenweg wird dagegen die Punktzahl des Pärchens verwendet.

Das Paar GC hat einen Score von -3. (siehe BLOSUM50)

  • -16 + -8 = -24
  • -8 + -3 = -11
  • 8 + -8 = 0

Die höchste Punktzahl lässt sich also durch eine Lücke in der ersten Sequenz erreichen.

Auf diese Weise wird die Tabelle Zeile für Zeile gefüllt:

Nur ein Rechenweg hat zur höchstmöglichen Punktzahl geführt. Er beinhaltet sowohl Lücken in der ersten, als auch Lücken in der zweiten Sequenz.

Auswählen des Alignments (abstrakt)

Der zum letzten Feld führende Rechenweg muss nun aufgespürt werden. Dazu wird immer das Nachbarfeld ausgewählt, welches für die Berechnung verwendet wurde. (Die blaue Linie kennt der Algorithmus natürlich nicht.)

Ähnlich wie bei der Berechnung der Tabelle, wird das Nachbarfeld gewählt, durch das die (höchste) Punktzahl errechnet wurde. In diesem Fall das links-oben-Feld. Das entsprechende Aminosäuren-Paar wird dem fertigen Alignment (im Bild unten rechts) hinzugefügt. (Merke: diagonal: Match, links: Lücke im Ersten, links: Lücke im Zweiten)

Das gewählte Feld ist als nächstes dran:

Hier ergibt sich die höchste Punktzahl durch eine Lücke in der ersten Sequenz, also geht’s mit dem linken Feld weiter.

Schließlich gelangt man wieder beim ersten Feld an und hat das korrekte Alignment zusammengesetzt:

Du kannst das Programm auch herunterladen und die Berechnung schrittweise nachverfolgen: (falls es nicht starten sollte, musst du wahrscheinlich das .NET Framework 4 Client Profile nachinstallieren – der Installer ist auch dabei)

Wenn du im Programm bist, kannst du auswählen, dass die Berechnung nur schrittweise durchgeführt wird (None, FMatrix, Alignment, Both). Mit dem “calculate”-Knopf wird gestartet und mit “next” geht’s einen Rechenschritt weiter. Wenn du mit der Maus über eine der Zahlen fährst, erscheint die Berechnung des Feldes.

Die F-Matrix (Code)

Der Code für den Needleman-Wunsch Algorithmus ist etwas ausführlicher, als die vorherigen Beispiele, daher habe ich ihn hier auf drei Methoden aufgeteilt:

  • AlignSequenccesAsync -> wird aufgerufen um die Sequenzen zu berechnen
  • CalculateFMatrix -> berechnet aus zwei Sequenzen die F-Matrix
  • SelectAlignment -> wählt aus einer F-Matrix das Alignment aus

Beginnen wir zunächst mit dem Berechnen der F-Matrix:

Oben haben wir gesehen, wie die F-Matrix manuell berechnet werden kann. Bei Sequenzen mit mehreren Tausend Aminosäuren ist das natürlich nicht mehr machbar.

In C# verwenden wir für die F-Matrix ein zweidimensionales int-Array, welches in Zeile 35 initialisiert wird.

Zunächst werden in Zeile 37-41 die jeweils erste Zeile bzw. Spalte der Tabelle gefüllt. Die erste Zelle (gap vs. gap) bekommt hier ausnahmsweise keine gap-penalty – gap-gap (am Anfang des Alignments) macht schließlich auch keinen Sinn. Für die restlichen Zellen der Spalte bzw. Zeile, wird für die Punktzahl zur Berechnung nur die gap-penalty verwendet, schließlich treten auf dem Weg zur Zelle keine echten Paare auf.
Für die übrigen Zellen wird der im vorherigen Kapitel beschriebene Rechenweg durchgeführt: In den Zeilen 47-49 werden die möglichen Punktzahlen aus den umliegenden Feldern berechnet. Die höchste wird anschließend ausgewählt und in der Tabelle (f) gespeichert (Zeile 55).

Auswählen des Alignments (Code)

Die F-Matrix enthält nun alle Informationen, die zur Auswahl des idealen Alignments benötigt werden. Beginnend mit der letzten Zelle, wird nun jeweils die Differenz zu den drei anderen Zellen berechnet (scoreDiag, scoreUp, scoreLeft in Zeile 65-68). Anschließend wird geprüft, ob die jeweilige Nachbarzelle für die Berechnung verwendet wurde. Für die oben, bzw. links liegende Zelle muss die Differenz zur aktuellen Zelle der gap-penalty entsprechen, während die Differenz zur oben-links-Zelle dem Score für das aktuelle Paar entspricht.

Das fertige Alignment (alignmentA, alignmentB) wird mit dem entsprechenden Paar verlängert. Die Zählvariablen i und j werden nun verringert, sodass das gewählte Nachbarfeld als nächstes dran ist. (Für diagonal beide verringern; nach oben j verringern; nach links i verringern) (Zeile 69-87)

Sobald eine der beiden Variablen i, oder j bei 0 angekommen ist (man ist am Ende einer Sequenz angelangt), muss der Rest der verbleibenden Sequenz mit gaps alignt werden. (Zeile 89-100)

alignmentA und alignmentB enthalten nun die berechneten Sequenzen, sind allerdings noch in umgekehrter Reihenfolge. Das Umkehren der Reihenfolge wird in der AlignSequencesAsync-methode durchgeführt. Dazu wird die Methode Reverse-String verwendet, auf die ich jetzt nicht weiter eingehe.

AlignSequencesAsync verknüpft CalculateFMatrix und SelectAlignment:

Anfangs (Zeile 15+16) sind die berechneten Sequenzen leer (“”). Die eigentliche Berechnung wird auf einem neuen Thread durchgeführt. Das wird so gemacht, damit das Programm auch bei längeren Berechnung noch ‘responsive’ bleibt und es nicht so aussieht, als sei es abgestürzt.

In den Zeilen 24 und 25 wird das berechnete Alignment umgekehrt – SelectAlignment geht schließlich rückwärts durch die Tabelle.

Nachdem alignmentTask fertig ist (Zeile 28) wird das fertige Alignment als string[] zurückgegeben (Zeile 29).

So viel zur Theorie. Das Beispielprojekt zum Selbermachen folgt in Kürze.

02 Scoring von Alignments

  1. Einführung in die Bioinformatik
  2. Scoring von Alignments
  3. Der Needleman-Wunsch-Algorithmus

Prüfen auf Identität

Die einfachste Art, zwei Sequenzen miteinander zu vergleichen ist, zu prüfen, ob sie identisch sind. Dazu müssen jeweils die 0. Position der ersten Sequenz mit der 0. Position der zweiten, die 1. der ersten mit der 1. der zweiten und so weiter vergleichen werden:

Der folgende Code macht genau das gleiche, verwendet dabei jedoch statt einer for-Schleife eine while-Schleife:

while-Schleifen brauchen nicht nur mehr Zeilen, sondern sind auch gefährlicher, da man gerne mal das ‘i++;’ vergisst.

Das Ergebnis einer solchen Prüfung kann offensichtlich nur zwei Werte annehmen: true oder false.

Sowohl Mutationen, als auch Rasterverschiebungen führen bei dieser Methode zu einem ‘false‘:


Im folgenden Kapitel betrachten wir zunächst der ersten Fall und bewerten ein Alignment unter Berücksichtigung von Mutationen.

Bewerten von Mutationen

Welches der folgenden zwei Alignments ist das wahrscheinlichere?


Beide Alignments unterscheiden sich in genau einer Aminosäure. Um eine qualifizierte Aussage zu treffen, bei welchem es sich um das ‘bessere’ bzw. wahrscheinliche Alignment handelt, müssen wir den Austausch K<>P mit dem Austausch F<>A vergleichen.

Hierzu wird eine sogenannte ‘Substitution Matrix‘ verwendet. Dabei handelt es sich um eine Tabelle, in der Aminosäure-Paare (z.B. P-P, G-C, W-A..) eine Punktzahl (Score) zugewiesen wird. Paare gleicher Aminosäuren bekommen dabei eine positive Punktzahl, während eine Mutation in der Regel einen negativen Score bekommt. Es gibt verschiedene solcher Tabellen, die sich in ihrer Berechnung unterscheiden. Wir verwenden hier die BLOSUM50 Matrix. Berechnet wird der Score bei BLOSUM50 durch die Formel

Wobei p(ab) die Wahrscheinlichkeit für das Auftreten des Paares A-B in natürlichen Proteinsequenz-Alignments ist, während q(a) bzw. q(b) die Frequenz in zufälligen ist. Das Ergebnis wird zur nächsten Ganzzahl gerundet.

Der Score einer Sequenz berechnet sich aus der Summe der Scores aller Paare. Die Paarung einer Aminosäure mit einer Lücke (gap) ist ebenfalls zulässig und wird immer mit dem selben Score, der sogenannten gap-penalty bewertet. In der abgebildeten Tabelle hat diese den Wert -5.

In unserem Beispiel oben unterschieden sich die ersten beiden Sequenzen im Paar K‑P, welches den Wert ‑1 hat, während sich die folgenden zwei Sequenzen im Paar A‑F mit dem Wert ‑3 unterschieden. Der Score für das erste Alignment summiert sich damit auf 62, während der des zweiten 58 beträgt. (Man beachte, dass die korrekte Paarung von K‑K 6 Punkte, während die von F‑F 8 Punkte bringt.)

Die Sequenzen KIRSCHSAFT und PIRSCHSAFT haben damit eine größere Ähnlichkeit, als KIRSCHSAFT und KIRSCHSAAT.

Bewerten von Alignments

Das vorherige Kapitel hat schon einiges vorausgegriffen, doch soll nun auch gezeigt werden, wie die Berechnung des Scores ‘in großem Stil’ durchgeführt wird.

Ähnlich wie beim direkten Vergleich zweier Sequenzen, werden die Sequenzen in einer for-Schleife gelesen. Die int-Variable ‘score’ wird verwendet, um den Punktestand zu messen. In jedem Schritt wird der Punktestand um den entsprechenden Wert erhöht. Dazu muss auf die SubstitutionMatrix zugegriffen werden.

Um mit der SubstitutionMatrix arbeiten zu können, benötigen wir den Objekttyp Dictionary<Key, Value>.

Ein Dictionary<Key, Value> ähnelt einem Nachschlagewerk, bei dem jedes Element (Value) mit einem anderen Objekt (Key) identifiziert wird. Nehmen wir an, dass das Dictionary<char, int> mit der Bezeichnung ‘buchstaben’ das folgende Key-Value-Pair enthält: ‘C’, 3

buchstaben[‘C’] liefert damit den int-Wert 3 zurück.

Bei der SubstitutionMatrix handelt es sich um ein Objekt des Typs Dictionary<char, Dictionary<char, int>>, also ein Dictionary<char, …>, welches als Value ein Dictionary<char, int> beinhaltet. Das äußere beinhaltet damit die Zeilen der SubstitutionMatrix (z.B. substimatrix[‘C’] ist die Zeile ‘C’), während das Innere die Einträge in der Zeile beinhaltet (z.B. substimatrix[‘C’][‘P’] ist der Score für ein C‑P-Paar – also ‑4).

Sowohl im folgenden Codebeispiel, als auch im herunterladbaren Beispielprojekt, wird die BLOSUM50-Substitutions Matrix mit ‘blosum50matrix’ bezeichnet. Wie dieses Objekt zustande kommt, kannst du dir im Code anschauen, ist hier aber nicht weiter von Bedeutung.

Wichtig ist, dass wir in Zeile 207 überprüfen, ob wir bereits am Ende einer der beiden Sequenzen angelangt sind, bzw. ob das Zeichen an der Position ‘-‘, also eine gap ist. In diesem Fall müssen wir die gap penalty verwenden. Andernfalls wird der score in Zeile 210 um den Wert des Paares erhöht, der in der BLOSUM50 nachgesehen wird.

Mit der oben beschriebenen Methode kann nun Berechnet werden, wie gut ein Alignment ist.

Weiter geht es mit dem Needleman-Wunsch Algorithmus.