Het bepalen van het volledige genoom van een organisme (genoomsequenering) is één van de hoekstenen van de bioinformatica. Helaas beschikken we nog steeds niet over microscopische technologie die toelaat om tot op nucleotideniveau in te zoomen en zo de reeks nucleotiden van een genoom één voor één af te lezen. Onderzoekers beschikken echter wel over chemische methoden die kunnen toegepast worden voor het genereren en identificeren van kortere DNA fragmenten. In deze context worden de korte fragmenten reads genoemd. Nadat we een grote collectie van reads geïdentificeerd hebben uit meerdere kopieën van hetzelfde genoom, blijft de uitdaging om het genoom te reconstrueren uit deze korte stukjes DNA. Dit proces wordt genoomassemblage genoemd.
Genoomassemblage is computationeel gezien een extreem moeilijk probleem. Het wordt nog moeilijker doordat heel veel genomen een groot aantal identieke sequenties bevatten die op verschillende plaatsen in het genoom herhaald worden. Dergelijke herhalingen zijn vaak duizenden nucleotiden lang en sommige kunnen op duizenden verschillende plaatsen in het genoom voorkomen. Dit komt vooral voor in de grote genomen van planten en dieren. Hierdoor is het vaak niet mogelijk om het volledige genoom te reconstrueren, en eindigt het assemblageproces met een aantal grote stukken van het genoom die in deze context contigs genoemd worden.
Opgave
Om de kwaliteit van een genoomassemblage te bepalen (bijvoorbeeld om twee verschillende assemblage-algoritmen te vergelijken, die elk afzonderlijk contigs bepaald hebben vertrekkend van dezelfde verzameling reads) wordt vaak gebruikgemaakt van de N50 statistiek.
Stel dat we de lijst van lengtes van de contigs van een genoomassemblage aanduiden als $$L$$ (dit is dus een lijst van natuurlijke getallen), dan kan de N50 statistiek als volgt berekend worden:
maak een nieuwe lijst $$L'$$ die $$n$$ kopieën bevat van elk element $$n$$ uit de originele lijst $$L$$
de N50 statistiek is dan gelijk aan de mediaan1 van $$L'$$
Gevraagd wordt:
Schrijf een functie mediaan waaraan een collectie (een lijst, tuple, verzameling, …) van getallen moet doorgegeven worden. De functie moet de mediaan van deze collectie teruggeven als een floating point getal.
Schrijf een functie uitbreiding waaraan een collectie (een lijst, tuple, verzameling, …) van natuurlijke getallen moet doorgegeven worden. De functie moet een nieuwe lijst teruggeven, die $$n$$ kopieën bevat van elk element $$n$$ uit de gegeven collectie.
Gebruik de functies mediaan en uitbreiding om een functie N50 te schrijven. Aan deze functie moet een collectie (een lijst, tuple, verzameling, …) van natuurlijke getallen doorgegeven worden, die de lengtes van de contigs van een genoomassemblage voorstellen. De functie moet de N50 statistiek voor deze collectie van contiglengtes teruggeven.
Mediaan
De mediaan van een lijst getallen is het getal dat in het midden staat als de lijst oplopend of aflopend gesorteerd wordt. Als de lijst een even aantal getallen bevat, dan wordt de mediaan bepaald als het gemiddelde van de twee middelste getallen van de gesorteerde lijst.
Voorbeeld
>>> contigs = (2, 2, 2, 3, 3, 4, 8, 8)
>>> mediaan(contigs)
3.0
>>> uitbreiding(contigs)
[2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]
>>> N50(contigs)
6.0