Het genoom van een levend organisme bestaat uit een opeenvolging van genen. Deze genen coderen voor de eiwitten die het functioneren van de cellen sturen waaruit het organisme is opgebouwd. Genen kunnen voorwaarts of achterwaarts georiëenteerd zijn en overlappen elkaar niet. Tussen twee genen kunnen fragmenten liggen die niet coderen voor eiwitten. Deze niet-coderende fragmenten worden soms ook junk DNA genoemd. Een genoomfragment wordt grafisch op de volgende manier voorgesteld:

• Het aantal symbolen dat gebruikt wordt voor de grafische voorstelling van een gen of een niet-coderend fragment staat in verhouding tot de lengte ervan op het genoom.

• Een voorwaarts gen wordt voorgesteld door nul of meer opeenvolgende gelijktekens (=) gevolgd door een groter dan teken (>). Zo wordt een voorwaarts gen van lengte vier voorgesteld door de tekenreeks ===> en stelt de tekenreeks > een voorwaarts gen van lengte één voor.

• Een achterwaarts gen wordt voorgesteld door een kleiner dan teken (<) gevolgd door nul of meer opeenvolgende gelijktekens (=).

• Een niet-coderend fragment wordt voorgesteld door één of meer opeenvolgende koppeltekens (-).

• Wanneer een achterwaarts gen onmiddellijk gevolgd wordt door een voorwaarts gen — zonder tussenliggend niet-coderend fragment — en wanneer bovendien minstens één van beide genen minstens lengte twee heeft, dan worden deze genen in de grafische voorstelling van elkaar gescheiden door een verticale streep (|). Op die manier kan ondubbelzinnig bepaald worden welke gelijktekens bij welk gen behoren. De grafische voorstelling <==> kan immers dubbelzinnig geïnterpreteerd worden als <|==>, <=|=> of <==|>. De grafische voorstelling <> kan daarentegen niet dubbelzinnig geïnterpreteerd worden, en stelt een achterwaarts gen van lengte één voor, gevolgd door een voorwaarts gen van lengte één.

Zo is de tekenreeks ----==>--<===--<==|===>---- de grafische voorstelling van een genoomfragment met een voorwaarts gen, gevolgd door twee opeenvolgende achterwaartse genen, gevolgd door een voorwaarts gen. Alle genen worden hierbij gescheiden door niet-coderende fragmenten, behalve de laatste twee genen. Omdat deze laatste twee genen een voorbeeld vomen van het geval beschreven in het laatste puntje in bovenstaande lijst, moet er in de grafische voorstelling een verticale streep tussen beide genen geplaatst worden.

Opgave

Elke regel van het bestand genome.txt¹ bevat de grafische voorstelling van een genoomfragment, gevolgd door een spatie en een woord dat enkel bestaat uit letters van het alfabet. Alle genoomfragmenten bevatten minstens twee genen. Gevraagd wordt:

1. Bepaal reguliere expressies voor elk van de onderstaande verzamelingen, waarbij $$\mathcal{G}$$ de verzameling voorstelt van grafische voorstellingen voor genoomfragmenten met minstens twee genen in het formaat dat hierboven werd beschreven. Probeer deze reguliere expressies zo kort mogelijk te houden.

   • $$\alpha = \{ g \in \mathcal{G}\,|\,$$ eerste en laatste gen van $$g$$ hebben dezelfde oriëntatie $$\}$$

     voorbeelden:	--===><===<===-----==>--- $$\in \alpha$$
     	<====|==>----<=---===> $$\not\in \alpha$$

   • $$\beta = \{ g \in \mathcal{G}\,|\,$$ $$g$$ bevat geen opeenvolgende genen met dezelfde oriëntatie $$\}$$

     voorbeelden:	<====|==>----<=---===> $$\in \beta$$
     	--===><===<===-----==>--- $$\not\in \beta$$

   • $$\gamma = \{ g \in \mathcal{G}\,|\,$$ alle genen in $$g$$ worden steeds gescheiden door een niet-coderend fragment $$\}$$

     voorbeelden:	====>-----<====-<==---<== $$\in \gamma$$
     	----====>-<|====>-=>><=<==== $$\not\in \gamma$$

   • $$\delta = \{ g \in \mathcal{G}\,|\,$$ | opeenvolgende genen met tegengestelde oriëntatie worden in $$g$$ steeds gescheiden door een niet-coderend fragment met lengte minstens drie $$\}$$

     voorbeelden:	--<===----=> $$\in \delta$$
     	--===>--<= $$\not\in \delta$$

   Gebruik een commando uit de grep familie om enkel die regels van het bestand genome.txt² te selecteren met grafische voorstellingen van genoomfragmenten die behoren tot de opgegeven verzameling.

2. Beschouw de verzamelingen $$\alpha$$, $$\beta$$, $$\gamma$$ en $$\delta$$ zoals hierboven gedefinieerd. Gebruik nu deze verzamelingen om op de volgende manier een boodschap bestaande uit vier woorden te achterhalen:

   • Het eerste woord staat op de unieke regel met een genoomfragment uit de verzameling $$\alpha \cap \beta$$

   • Het tweede woord staat op de unieke regel met een genoomfragment uit de verzameling $$\beta \cap \gamma$$

   • Het derde woord staat op de unieke regel met een genoomfragment uit de verzameling $$\gamma \cap \delta$$

   • Het vierde woord staat op de unieke regel met een genoomfragment uit de verzameling $$\delta \cap \alpha$$

   Geef telkens een Unix commando dat elk van deze woorden opzoekt in het bestand en uitschrijft naar standaard uitvoer (zonder het patroon dat aan het woord voorafgaat). Hierbij is het dus niet toegelaten om het woord letterlijk uit te schrijven (bv. echo xxx).