4. Vorlesung WS 2006/07Softwarewerkzeuge1 V4 – Analyse von Genomsequenzen - Gene identifizieren z.B. Hidden Markov Modelle - Transkriptionsfaktorbindestellen

4. Vorlesung WS 2006/07

Softwarewerkzeuge 1

V4 – Analyse von Genomsequenzen

- Gene identifizieren

z.B. Hidden Markov Modelle

- Transkriptionsfaktorbindestellen identifizieren

Position Specific Scoring Matrices (PSSM)

- finde Repeat-Sequenzen

Suche nach bekannten Repeat-Motiven

- Genom-Assemblierungfinde identische k-Tupel

- Genom-AlignmentSuche nach MUMs (maximal unique matches)


Softwarewerkzeuge 2

Einleitung – Gene identifizieren

Die einfachste Methode, DNA Sequenzen zu finden, die für Proteine kodieren, ist

nach open reading frames (ORFs) zu suchen.

In jeder Sequenz gibt es 6 mögliche open reading frames::

3 ORFs starten an den Positionen 1, 2, und 3 und gehen in die 5‘ 3‘ Richtung,

3 ORFs starten an den Positionen 1, 2, und 3 und gehen in die 5‘ 3‘ Richtung des

komplementären Strangs.

In prokaryotischen Genomen werden Protein-kodierende DNA-Sequenzen

gewöhnlich in mRNA transkribiert und die mRNA wird ohne wesentliche

Änderungen direkt in einen Aminosäurestrang übersetzt.

Daher ist der längste ORF von dem ersten verfügbaren Met codon (AUG) auf der

mRNA bis zu dem nächsten Stopcodon in demselben offenen Leserahmen,

gewöhnlich eine gute Vorhersage für die Protein-kodierende Region.


Softwarewerkzeuge 3

Methode

Erhalte neue genomische DNA-Sequenz

Übersetze sie in allen6 Leserahmen und vergleiche sie mit derDatenbank für Protein-sequenzen.

Führe Suche in EST-Datenbank oder cDNA-Datenbank desselbenOrganismus nachähnlichen Sequenzendurch, falls verfügbar.

Benutze Genvorhersage-programm um Gene zufinden

Analysiere regulatorischeSequenzen des Gens.


Softwarewerkzeuge 4

Extrinsische und intrinsische Methoden

Viele Verfahren kombinieren nun

(a) Homologie-Methoden = „extrinsische Methoden“ mit

(b) Genvorhersage-Methoden = „intrinsische Methoden“

Etwa die Hälfte aller Gene kann durch Homologie zu anderen bekannten Genen oder

Proteinen gefunden werden (dieser Anteil wächst stetig, da die Anzahl an sequenzierten

Genomen und bekannten cDNA/EST Sequenzen kontinuierlich wächst.)

Um die übrige Hälfte an Genen zu finden, muß man prädiktive Methoden einsetzen.

Mathé et al. Nucl. Acids. Res. 30, 4103 (2002)


Softwarewerkzeuge 5

Beispiel: Vergleich von Glimmer und GeneMarksS

Besemer et al. Nucl. Acids. Res. 29, 2607 (2003)


Softwarewerkzeuge 6

Hidden Markov Models

Ein Hidden Markov Modell ist ein Graph,

der verschiedene Zustände verbindet.

Jeder Zustand kann möglicherweise eine

Reihe an Beobachtungen „aussenden“.

Der Prozeß entwickelt sich in eine

Richtung, z.B. die Zeit.

Man parametrisiert das Modell mit

Wahrscheinlichkeit für den Zustand zur

Zeit t + 1, gesetzt dass die Zustände

davor bekannt sind.


Softwarewerkzeuge 7

TIGR: GlimmerM, Exonomy and Unveil

Topologies of Unveil Exonomy

283-state HMM 23-state GHMM

Majoros et al. Nucl. Acids. Res. 31, 3601 (2003)


Softwarewerkzeuge 8

Methoden funktionieren nicht überall

Ein Beispiel, in dem Exonomy die

Gene richtig erkennt.

Ein Beispiel, in dem GlimmerM die

Gene richtig erkennt.

Ein Beispiel, in dem Unveil die

Gene richtig erkennt (auch

Genscan).

Majoros et al. Nucl. Acids. Res. 31, 3601 (2003)


Softwarewerkzeuge 9

Zusammenfassung

Die Resultate der Genvorhersage werden zuverlässiger; dennoch sollte man sie

mit Vorsicht behandeln.

Sie sind sehr nützlich um die Entdeckung von Genen zu beschleunigen.

Dennoch sind biologische Techniken notwendig um die Existenz von virtuellen

Proteinen zu bestätigen und um dessen biologischen Funktion zu finden bzw. zu

beweisen.

Dadurch werden vergleichende Genom-Ansätze immer wichtiger, in denen

Programme Genkandidaten auf Homologie mit exprimierten Sequenzen

vergleichen (EST oder cDNA Sequenzdaten).

Neue Arbeiten wenden sich nun RNA-kodierenden Genen zu.

Mathé et al. Nucl. Acids. Res. 30, 4103 (2002)


Softwarewerkzeuge 10

Transkriptions – Gen-Regulationsnetzwerke

Die Maschine, die ein Gen

transkribiert, besteht aus etwa 50

Proteinen, einschließlich der RNA

polymerase, ein Enzym, das DNA

code in RNA code übersetzt.

Eine Gruppe von Transkriptions-

faktoren bindet an die DNA

gerade oberhalb der Stelle des

Kern-Promoters, während

assoziierte Aktivatoren an

Enhancer-Regionen weiter

oberhalb der Stelle binden.

ahttp://www.berkeley.edu/news/features/1999/12/09_nogales.html



Promoter prediction in E.coli

To analyze E.coli promoters, one may align a set of promoter sequences by the

position that marks the known transcription start site (TSS) and search for

conserved regions in the sequences.

E.coli promoters are found to contain 3 conserved sequence features

- a region approximately 6 bp long with consensus TATAAT at position -10

- a region approximately 6 bp long with consensus TTGACA at position -35

- a distance between these 2 regions of ca. 17 bp that is relatively constant

a



Feasibility of computational motif search?

Computational identification of transcription factor binding sites is difficult

because they consist of short, degenerate sequences that occur frequently by

chance.

The problem is not easy to define (therefore: it is „complex“) because

- the motif is of unknown size

- the motif might not be well conserved between promoters

- the sequences used to search for the motif do not necessarily represent the

complete promoter

- genes with promoters to be analyzed are in many cases grouped together by a

clustering algorithm which has its own limitations.



Strategy 1

Arrival of microarray gene-expression data.

Group of genes with similar expression profile (e.g. those that are activated at

the same time in the cell cycle) one may assume that this profile ist, at least

partly, caused by and reflected in a similar structure of the regions involved in

transcription regulation.

Search for common motifs in < 1000 base upstream regions.

Sofar used: detection of single motifs (representing transcription-factor binding

sites) common to the promoter sequences of putatively co-regulated genes.

Better: search for simultaneous occurrence of 2 or more sites at a given distance

interval! Search becomes more sensitive.



Motif-Identifizierung

A flowchart to illustrate the two

different approaches for motif

identification. We analyzed 800

bp upstream from the translation

start sites of the five genes from

the yeast gene family PHO by

the publicly available systems

MEME (alignment) and RSA

(exhaustive search). MEME was

run on both strands, one

occurrence per sequence mode,

and found the known motif

ranked as second best. RSA

Tools was run with oligo size 6

and noncoding regions as

background, as set by the demo

mode of the system. The well-

conserved heptamer of the

motifs used by MEME to build

the weight matrix is printed in

bold. Ohler, Niemann Trends Gen 17, 2 (2001)



Strategie 2: Erschöpfende Motivsuche in upstream-Regionen

Benutze Beobachtung daß relevante Motive sich in der upstream-Region oft

viele Mal wiederholen, unter Umständen mit kleinen Variationen, damit die

regulatorische Wirkung effektiv ist.

Suche in der upstream-Region nach überrepräsentierten Motiven

(1) Ordne Gene nach den überrepräsentierten Motiven.

(2) Analysiere Gruppen von Genen, die Motive für Ko-Regulation in Microarray-

Experimenten gemeinsam haben.

(3) Betrachte überrepräsentierte Motive, die Gruppen von koregulierten Genen

als mögliche Bindungsstellen markieren.

Cora et al. BMC Bioinformatics 5, 57 (2004)



Erschöpfende Motivsuche in upstream-Regionen

Exploit

Cora et al. BMC Bioinformatics 5, 57 (2004)



Aktuelle Verfahren um Promotoren zu finden

Ohler, Niemann Trends Gen 17, 2 (2001)



Positions-spezifische Gewichtsmatrix

Populäres Verfahren wenn es eine Liste von Genen gibt, die ein TF-Bindungs-

motiv gemeinsam haben. Gute MSAs müssen vorhanden sein.

Alignment-Matrix: wie häufig treten die verschiedenen

Buchstaben an jeder Position im Alignment auf?

Hertz, Stormo (1999) Bioinformatics 15, 563



Positions-spezifische Gewichtsmatrix

Beispiele für Matrizen, die von YRSA verwendet werden:

http://forkhead.cgb.ki.se/YRSA/matrixlist.html



http://www.rcsb.org

3D Strukturen von Transkriptionsfaktoren

1A02.pdb 1AM9.pdb 1AU7.pdb

1CIT.pdb 1GD2.pdb 1H88.pdb

TFs binden auf sehr

unterschiedliche Weise.

Manche sind sehr

selektiv für die

DNA-Konformation.

2 TFs bound!



Datenbank für eukaryotische Transkriptionsfaktoren: TRANSFAC

BIOBase / TU Braunschweig / GBF

Relationelle Datenbank

6 Dateien:

FACTOR Wechselwirkung von TFs

SITE ihre DNA-Bindungsstelle

GENE durch welche sie diese

Zielgene regulieren

CELL wo kommt Faktor in Zelle vor?

MATRIX TF Nukleotid-Gewichtungsmatrix

CLASS Klassifizierungsschema der TFs

Wingender et al. (1998) J Mol Biol 284,241





Matys et al. (2003) Nucl Acid Res 31,374




Matys et al. (2003) Nucl Acid Res 31,374




TRANSFAC Klassifizierung

1 Superklasse basische Domänen 3 Superklasse: Helix-turn-helix

1.1 Leuzin-zipper Faktoren (bZIP)

1.2 Helix-Loop-Helix Faktoren (bHLH) 4 Superklasse: beta-Scaffold

1.3 bHLH-bZIP Faktoren mit Kontakt in der

1.4 NF-1 Minor Groove

1.5 RF-X

1.6 bHSH 5 Superklasse: andere

2 Superklasse: Zink-koordinierende DNA-bindende Domänen

2.1 Cys4 Zinkfinger vom Typ nuklearer Rezeptor

2.2 verschiedene Cys4 Zinkfinger

2.3 Cys2His2 Zinkfinger Domänen

2.4 Cys6 Cystein-Zink Cluster

2.5 Zinkfinger mit abwechselnder Zusammensetzung

http://www.gene-regulation.com/pub/databases/transfac/cl.html



TRANSFAC Datenbank

Eintrag für 1.1 Leuzine-Zippers

http://www.gene-regulation.com



TRANSFAC Datenbank




TRANSFAC Datenbank




Zusammenfassung


Es gibt große Datenbanken (z.B. TRANSFAC) mit Informationen über

Promoterstellen. Diese Informationen sind experimentell überprüft.

Microarray-Daten erlauben es, nach gemeinsamen Motiven von ko-regulierten

Genen zu suchen.

Auch möglich: gemeinsame Annotation in der Gene Ontology etc.

TF-Bindungsmotive sind oft überrepräsentiert in der 1000 bp-Region upstream.

Die klare Funktion davon ist unbekannt.

Relativ wenige TFs regulieren eine große Anzahl an Genen.



Identifizierung von Repeats: RepeatMasker


RepeatMasker: durchsucht DNA Sequenzen auf

- eingefügte Abschnitte, die bekannten Repeat-Motiven entsprechen

(dazu wird eine lange Tabelle mit bekannten Motiven verwendet)

und

- auf Regionen geringer Komplexität (z.B. lange Abschnitt AAAAAAAA).

Output:

- detaillierte Liste, wo die Repeats in der Sequenz auftauchen und

- eine modifizierte Version der Input-Sequenz, in der die Repeats „maskiert“

sind, z.B. durch N‘s ersetzt sind.

Für die Sequenzvergleiche wird eine effiziente Implementation des Smith-

Waterman-Gotoh Algorithmus verwendet.



Whole Genome Shotgun Assemblierung

Es gibt 2 Strategien für die

Sequenzierung von Genomen:

clone-by-clone Methode

whole-genome shotgun Methode

(Celera, Gene Myers).

Die Shotgun Sequenzierung wurde

bereits 1977 von F. Sanger et al.

eingeführt und ist seither eine

Standardmethode für die

Sequenzierung von Genen.

Umstritten war jedoch, ob man sie

auch für komplette Genome

verwenden kann. ED Green, Nat Rev Genet 2, 573 (2001)



Arachne Programm

von Serafin Batzoglou (MIT, Doktorarbeit 2000)

(i) konstruiere Graph G für Überlappungen zwischen Paaren von reads aus

Shotgun-Daten

(i) prozessiere G um Supercontigs von gemappten reads zu erhalten.

Batzoglou et al. Genome Res 12, 177 (2002)

Wichtige Variation der whole-genome shotgun Sequenzierung:

sequenziere reads jeweils von beiden Enden eines Klons.

Da die Inserts nach ihrer Größe ausgewählt werden, ist damit der ungefähre

Abstand zwischen dem Paar von reads bekannt.

Man nennt diese earmuff (Ohrenwärmer) Verbindungen.



Arachne: erzeuge Überlappungsgraphen

Liste von reads R = (r1, ..., rN) , N ist die Anzahl der reads.

Jeder read ri besitzt eine Länge li < 1000.

Wenn beide reads von den Endpunkten desselben Klons stammen (earmuff link),

besitzt ri eine Verknüpfung zu einem anderen read rj in einer festen Distanz dij.

Erstes Ziel: erzeuge Graphen G der Überlappungen (Kanten) zwischen Paaren an

reads (Knoten) dies ergibt die Paare an reads in R, die aligniert werden müssen.

Da R sehr lang sein kann, sind N2 alignments nicht praktikabel.

erstelle Tabelle für das Vorkommen von k-Tupel (Strings der Länge k) in den reads,

zähle die Anzahl von k-Tupel Treffern für jedes Paar an reads.

Führe dann paarweise Alignments zwischen den Paaren an reads durch,

die mehr als cutoff gemeinsame k-mere besitzen.

Batzoglou PhD thesis (2002)



Arachne: Tabelle für Vorkommen von k-meren

Ermittle die Anzahl an k-Tupel Treffern in der Vorwärts- und Rückwärts-Richtung

zwischen jedem Paar von reads in R.

(1) Ermittle alle Triplets (r,t,v)

r = Nummer des reads in R

t = Index eines k-mers, das in r vorkommt

v = Richtung des Auftretens (vorwärts oder rückwärts)

(2) sortiere die Menge der Paare nach den k-mer Indices t

(3) verwende eine sortierte Liste um eine Tabelle T von Quadrubletts (ri, rj, f, v)

zu erstellen, wobei ri und ri die reads sind, die mindestens einen gemeinsamen

k-mer enthalten, v die Richtung angiebt, und f die Anzahl an gemeinsamen

k-mers zwischen ri und rj in Richtung v.




Arachne: Tabelle für Vorkommen von k-mers


Hier:k = 3



Arachne: Tabelle für Vorkommen von k-mers

Wenn ein k-Tupel „zu oft“ auftritt gehört er wahrscheinlich zu einer

Repeat-Sequenz.

Man sollte diese nicht für die Detektion von Überlappungen verwenden.

Implementierung

(1) finde k-Tupel (r,t,v) und sortieren sie in 64 Dateien entsprechen den ersten

drei Nukleotiden jedes k-mers.

(2) Für i=1,64

lade Datei in den Speicher, sortiere nach t, speichere sortierte Datei ab.

end

(3) lade 64 sortierte Dateien nacheinander in den Speicher,

fülle Tabelle T nacheinander auf.

In der Praxis ist k = 8 bis 24.Batzoglou PhD thesis (2002)



Arachne: paarweise read-Alignments

Führe paarweise Alignments zwischen den Reads durch, die mehr als Cutoff

gemeinsame k-mers besitzen.

Sobald man zu häufige k-mers ausschließt (mehr als ein zweiter Cutoff), ist

sichergestellt, daß nur O(N) viele paarweise Sequenzalignments durchgeführt

werden müssen.

Nur eine kleine Anzahl an Basen-Austauschen und Indels ist in einer

überlappenden Region zweier alignierter reads erlaubt.

Output des Alignment-Algorithmus:

für die reads ri, rj gibt es Quadrubletts (b1, b2, e1, e2) für jede detektierte

Überlappungsregion mit den Anfangspositionen b1, b2 und Endpositionen e1,e2.

Falls eine signifikante Überlappungsregion vorliegt, wird (ri, rj, b1, b2, e1, e2) eine

Kante im Überlappungsgraphen G. Batzoglou PhD thesis (2002)



Kombination teilweiser Alignments

3 teilweise Alignments der Länge

k=6 zwischen einem Paar von

reads werden zu einem einzigen

vollen Alignment der Länge k=19

kombiniert.

Die vertikalen Linien verbinden

übereinstimmenden Basen,

wogegen x Mismatche sind.

Dies ist eine oft auftretende

Situation, in der ein ausgedehnter

k-mer Treffer ein volles Alignment

von zwei reads ist.




Repeats erzeugen Mehrdeutigkeit

Ohne das Auftreten von Sequen-

zierungsfehlern und Repeats wäre es

einfach, alle entdeckbaren paarweise

Abstände von reads zu finden und

den Graph G zu konstruieren.

Da es Repeats jedoch sehr häufig

auftreten, bedeutet eine Verbindung

zwischen zwei reads in G nicht ohne

weiteres eine wahre Überlappung.

Eine „Repeat-Verbindung“ ist eine

Verbindung in G zwischen zwei

reads, die aus verschiedenen

Regionen des Genoms stammen und

in der repetitiven Sequenz überein-

stimmen. Batzoglou PhD thesis (2002)



Sequence contigs


unerläßlich für die Assemblierung ist die ausreichende Überdeckung (mehrfache

Sequenzierung = coverage) derselben Genomregionen



Verbinden von Contigs


Sequenz-Contigs werden gebildet

indem Paare von reads verbunden

werden, die eindeutig verbunden

werden können.

Tatsächlich ist die Situation viel

schwieriger als hier gezeigt, da

Repeats häufig nicht zu 100%

zwischen Kopien konserviert sind.

Durch die Löschung von k-mers hoher Frequenz wird einiges an Repetition im

Genom vor der Erzeugung von G effizient maskiert.

Zur Erkennung von repetitiven Verbindung dienen weitere heuristische Algorithmen,

die hier nicht diskutiert werden sollen.



Benutze Überlapp-Paarungen um die reads zu verbinden

Arachne sucht nach 2 Plasmiden mit

gleicher Insert-Länge, deren

Sequenzen an beiden Enden

überlappen paired pairs.


(A) A paired pair of overlaps.

The top two reads are end sequences from

one insert, and the bottom two reads are

end sequences from another.

The two overlaps must not imply too

large a discrepancy between the insert

lengths.

(B) Initially, the top two pairs of reads

are merged. Then the third pair of

reads is merged in, based on having

an overlap with one of the top two left

reads, an overlap with one of the top

two right reads, and consistent insert

lengths. The bottom pair is similarly

merged.

Unten: eine Menge von paired pairs

werden zu contigs zusammengefasst

und eine Konsensussequenz erzeugt.



Detection of repeat contigs

Contig R is linked to contigs A and

B to the right. The distances

estimated between R and A and

R and B are such A and B cannot

be positioned without substantial

overlap between them. If there is

no corresponding detected overlap

between A and B then R is

probably a repeat linking to two

unique regions to the right.


Some of the identified contigs are repeat contigs in which nearly identical

sequence from distinct regions are collapsed together. Detection by

(a) repeat contigs usually have an unusually high depth of coverage.

(b) they will typically have conflicting links to other contigs.

After marking repeat contigs, the remaining

contigs should represent the correctly

assembled sequence.



Contig assembly

If (a,b) and (a,c) overlap, then

(b,c) are expected to overlap.

Moreover, one can calculate that

shift(b,c)=shift(a,c)-shift(a,b).

A repeat boundary is detected

toward the right of read a, if there

is no overlap (b,c), nor any path

of reads x1, ..., xk such that (b,x1),

(x1,x2) ..., (xk,c) are all overlaps,

and shift(b,x1) + ... + shift(xk,c)

shift(a,c) – shift(a,b).




Consistency of forward-reverse links

(A) The distance d(A,B) (length of

gap or negated length of

overlap) between two linked

contigs A and B can be

estimated using the forward-

reverse linked reads between

them.

(B) The distance d(B,C) between

two contigs B,C that are

linked to the same contig A

can be estimated from their

respective distances to the

linked contig.




Contig Coverage and Read Usage




Characterization of Contigs and Supercontigs




Base Pair Accuracy


base quality x*10 means that (on average) one sequencing error occursin 10-x bases.



Computational Performance




Vergleich verschiedener Assemblierungen

Pevzner, Tang, Waterman PNAS 98, 9748 (2001)

man sollte gucken nach:

- welche Methode gibt die kleinste Anzahl an Contigs bzw. die kleinesten Anzahl

am festen Contigs bzw. falsch assemblierten Contigs- die größt mögliche Abdeckung durch Contigs- falsch assemblierte Contigs sollten einen möglichst geringen Teil des Genoms

ausmachen.



There is no error-free assembler to date

Pevzner, Tang, Waterman PNAS 98, 9748 (2001)

Comparative analysis of EULER, PHRAP, CAP, and TIGR assemblers (NM sequencing project). Every box corresponds to a contig in NM assembly produced by these programs with colored boxes corresponding to assembly errors. Boxes in the IDEAL assembly correspond to islands in the read coverage. Boxes of the same color show misassembled contigs. Repeats with similarity higher than 95% are indicated by numbered boxes at the solid line showing the genome. To check the accuracy of the assembled contigs, we fit each assembled contig into the genomic sequence. Inability to fit a contig into the genomic sequence indicates that the contig is misassembled. For example, PHRAP misassembles 17 contigs in the NM sequencing project, each contig containing from two to four fragments from different parts of the genome.

„Biologists "pay" for these errors at the

time-consuming finishing step“.



Whole Genome Alignment (WGA)

Nachdem die genomische DNA-Sequenz eng verwandter Organismen verfügbar

wird, ist die erste Frage, wie das Alignment zweier Genome aussieht.

Globale Genom-Alignments machen nur für eng verwandte Organismen Sinn.

Im anderen Fall muß man erst die genomischen Rearrangements betrachten.

Dann kann man die systenischen Regionen (Regionen, in denen Gen-

Reihenfolge des nächsten gemeinsamen Vorfahrens in beiden Spezies konserviert

blieb) betrachten und lokale Genom-Alignments dieser Regionen produzieren.



The mouse genome. Nature 420, 520 - 562

Konservierung von Syntenie zwischen Mensch und Maus

Ein typisches 510-kb Segment des Maus-Chromosoms 12, das mit einem

600-kb Stück des menschlichen Chromosom 14 verwandt ist.

Blaue Linien: reziprok eindeutige Treffer in beiden Genomen.

Rote Markierungen kennzeichnen die Länge der passenden Regionen.

Die Abstände zwischen diesen „Landmarks“ sind im Maus-Genom kleiner als

im Mensch, was mit der 14% kürzeren Gesamtlänge des Genoms

übereinstimmt.



The mouse genome. Nature 420, 520 - 562

Entsprechung syntenischer Regionen

342 Segmente und 217 Blöcke >300 kb mit konservierter Syntenie im Mensch

sind im Maus-Genom markiert.

Jede Farbe entspricht einem bestimmten menschlichen Chromosom.



Sensitivität

Couronne, ..., Dubchak, Genome Res. 13, 73 (2003)

Im globalen Mensch:Maus Alignment sind mehr als eine Millionen Regionen

stärker als 70% konserviert (auf 100-bp Level)

– diese Regionen decken > 200 Million bp ab.

Nur 62% von ihnen werden von (lokalen) BLAT-Treffern abgedeckt.

Dies bedeutet, daß man 38% der konservierten Abschnitte nur durch das globale

Alignment finden kann!

Idee: lokales Alignment soll als Anker-Verfahren für anschliessendes globales

Alignment dienen. Dadurch hofft man, viele zusätzliche konservierte Regionen

ausserhalb der Anker-Regionen zu finden.



hohe Sensitivität von globalen Alignments

Couronne, ..., Dubchak, Genome Res. 13, 73 (2003)

Beispiel: das globale Alignment der mouse finished sequence

NT_002570 gegen die Region, die mit BLAT-Ankern gefunden

wurde, zeigt konservierte kodierende und nicht-kodierende

Elemente, die mit BLAT nicht gefunden wurden.



Ankerbasierte Methoden für WGA

Diese Methoden versuchen sich entsprechende Teile der Buchstabenfolgen der

betrachteten Sequenzen zu finden, die wahrscheinlich zu einem globalen

Alignment gehören werden.

(Diese teilweisen Treffer können durch lokale Alignments gefunden werden).

Sie bilden „Anker“ in den beiden zu alignierenden Sequenzen.

In diesen Methoden werden zuerst die Ankerpunkte aligniert und dann die

Lücken dazwischen geschlossen.

MUMmer ist eine sehr erfolgreiche Implementation dieser Strategie für das

Alignment zweier genomischer Sequenzen.



Was ist MUMmer?

• A.L. Delcher et al. 1999, 2002 Nucleic Acids Res.

• http://www.tigr.org/tigr-scripts/CMR2/webmum/mumplot

• Nimm an, dass zwei Sequenzen eng verwandt sind (sehr ähnlich)

• MUMmer kann zwei bakterielle Genome in weniger als 1 Minute alignieren

• nutzt Suffix-Bäume um Maximal Unique Matches zu finden

• Definition eines Maximal Unique Matches (MUM):

– Eine Subsequenz, die in beiden Sequenzen genau einmal ohne Abweichungen vorkommt und in keine Richtung verlängert werden kann.

• Grundidee: ein MUM ausreichender Länge wird sicher Teil eines globalen Alignments sein.

A maximal unique matching subsequence (MUM) of 39 nt (shown in uppercase) shared by

Genome A and Genome B. Any extension of the MUM will result in a mismatch.

By definition, an MUM does not occur anywhere else in either genome. Delcher et al. Nucleic Acids Res 27, 2369 (1999)



MUMmer: wichtige Schritte

• Erkenne MUMs (Länge wird vom Benutzer festgelegt)

ACTGATTACGTGAACTGGATCCAACTCTAGGTGAAGTGATCCA

ACTGATTACGTGAACTGGATCCAACTCTAGGTGAAGTGATCCA

ACTGATTACGTGAACTGGATCCA

ACTC--TAGGTGAAGTG-ATCCA

1 10

1 10

20

20



Definition von MUMmers

• Für zwei Strings S1 und S2 und einen Parameter l

• Der Substring u ist eine MUM Sequenz wenn gilt: |u| > l u kommt genau einmal in S1 und genau einmal in S2 (Eindeutigkeit) Für jeden Buchstaben a kommt weder ua noch au sowohl in

S1 als auch in S2 vor (Maximalität)



Wie findet man MUMs?

• Naiver Ansatz

– Vergleiche alle Teilsequenzen von A mit allen Teilsequenzen von B.

Dies dauert O(nn)

• verwende Suffix-Bäume als Datenstruktur

– ein naiver Ansatz, einen Suffix-Baum zu konstruieren hat

eine quadratische Komplexität in der Rechenzeit und dem Speicherplatz

– durch klevere Benutzung von Pointern gibt es lineare Algorithmen in

Rechenzeit und Speicherplatz wie den Algorithmus von McCreight



Suffix-Bäume

CACATAG$

Suffix-Bäume sind seit über 20

Jahren wohl etabliert.

Einige ihrer Eigenschaften: • ein “Suffix” beginnt an jeder

Position I der Sequenz und reicht

bis zu ihrem Ende. • Eine Sequenz der Länge N hat N

Suffices.• Es gibt N Blätter.• Jeder interne Knoten hat mindest

zwei Kinder.• 2 Kanten aus dem selben Knoten

können nicht mit dem selben

Buchstaben beginnen.• Am Ende wird $ angefügt



Konstruktion eines Suffix-Baums

CACATAG$

CA

T

CA

G$

1

A

Suffixes:

1. CACATAG$




CACATAG$

Suffixes:

1. CACATAG$2. ACATAG$

CA

T

CA

G$

A

T

CA

G$

A

12

A




CACATAG$

Suffixes:

1. CACATAG$2. ACATAG$3. CATAG$

CA

T

CA

G$

A

T

CA

G$

T

G

$

AA

123

A




CACATAG$

Suffixes:

1. CACATAG$2. ACATAG$3. CATAG$4. ATAG$

CA

T

CA

G$

A

T

CA

G$

T

G

$

AA

T G $A

123

4

A




CACATAG$

Suffixes:

1. CACATAG$2. ACATAG$3. CATAG$4. ATAG$5. TAG$

CA

T

CA

G$

A

T

CA

G$

TT

A

G

$G

$

AA

T G $A

123

4

5

A




CA

T

CA

G$

A

T

CA

G$

TT

A

G

$G

$

AA

T G $A

G

$

123

4

5

6A

CACATAG$

Suffixes:

1. CACATAG$2. ACATAG$3. CATAG$4. ATAG$5. TAG$6. AG$




CA

T

CA

G$

A

T

CA

G$

TT

A

G

$G

$

AA

T G $A

G

$

G $

123

4

5

6

7

A

CACATAG$

Suffixes:

1. CACATAG$2. ACATAG$3. CATAG$4. ATAG$5. TAG$6. AG$7. G$




CA

T

CA

G$

A

T

CA

G$

TT

A

G

$G

$

AA

T G $A

G

$

G $$

123

4

5

6

78CACATAG$

A

Suffixes:

1. CACATAG$2. ACATAG$3. CATAG$4. ATAG$5. TAG$6. AG$7. G$8. $



Suchen in einem Suffix-Baum

CA

T

CA

G$

A

T

CA

G$

TT

A

G

$G

$

AA

T G $A

G

$

G $$

123

4

5

6

78

A

Search Pattern:CATA



Suchen in einem Suffix-Baum

CA

T

CA

G$

A

T

CA

G$

TT

A

G

$G

$

AA

T G $A

G

$

G $$

123

4

5

6

78

A

Search Pattern:ATCG



Sortieren der MUMs

• MUMs werden nach ihren Positionen in Genom A sortiert

1 2 3 4 5 6 7

1 3 2 4 6 7 5

Genome A:

Genome B:

1 2 4 6 7

1 2 46 7

Genome A:

Genome B:

Jeder MUM ist nur mit seiner Nummer gekennzeichnet, ohne Berücksichtigung seiner Länge.

Das obere Alignment zeigt alle MUMs.

Die Verschiebung von MUM 5 in Genom B zeigt eine Transposition an.

Die Verschiebung von MUM 3 könnte ein Zufallstreffer oder Teil einer inexakten Repeat-Sequenz sein.

Unteres Alignment: suche in beiden Genomen die längste gemeinsam ansteigende Folge an

Subsequenzen



Beispiel: Alignment zweier Mikroorganismen

Delcher et al. Nucleic Acids Res 27, 2369 (1999)

Das Genom von M.genitalium ist nur etwa 2/3 so

lang wie das von M.pneumoniae.

Obere Abbildung: FASTA-Alignment von

M.genitalium und M.pneumoniae.

Mitte: Alignment mit 25mers

Unten: Alignment mit MUMs. 5 Translokationen.

Ein Punkt bedeutet jeweils einen Treffer zwischen

den Genomen.

FASTA-Plot: ähnliche Gene

25-mer-Plot: 25-Basen-Sequenz, die in beiden

Sequenzen genau einmal vorkommt.

MUM-Plot: MUM-Treffer.



Beispiel: Alignment Mensch:Maus

Delcher et al. Nucleic Acids Res 27, 2369 (1999)

Alignment von weiter entfernt

liegenden Spezies:

Mensch gegen Maus.

Hier: Alignment einer 222 930 bp

Teilsequenz auf dem mensch-

lichen Chromosom 12, accession

no. U47924, gegen eine 227 538

bp lange Teilsequenz des Maus-

chromosoms 6.

Jeder Punkt des Plots entspricht

einem MUM von [ge]15 bp.



Zusammenfassung

• Die Anwendung der Suffix-Bäume war ein Durchbruch für die

Alignierung ganzer Genome

• MUMmer 2 besitzt zusätzliche Verbesserung für die Rechenzeit und

den Speicherplatz

– die Verwendung von Suffix-Arrays anstatt von Suffix-Bäumen gibt

eine verbesserte Datenstruktur ( Stefan Kurtz, Hamburg)

– es wird nun möglich, mehr als zwei Genome zu alignieren

(implementiert in MGA)

Documents

4. Vorlesung WS 2006/07Softwarewerkzeuge1 V4 – Analyse von Genomsequenzen - Gene identifizieren z.B. Hidden Markov Modelle - Transkriptionsfaktorbindestellen