Inklusion/Exklusion: DNA Sequenzen

24.09.2010, 12:05

OVetS

Inklusion/Exklusion: DNA Sequenzen

Meine Frage:
Hallo!

Ich versuche gerade das Prinzip der Inklusion/Exklusion zu verstehen.
Die Aufgabe die mir da nun Probleme bereitet ist folgende.
Eine DNA Sequenz ist ein Wort über dem Alphabet {A,C,G,T}
Wieviele DNA Sequenzen der Länge n gibt es, in der jeder Buchstabe A,C,G,T min. einmal vorkommt?

Meine Ideen:
$\begin{eqnarray*} 4^{n} \end{eqnarray*}$ wäre doch die anzahl ohne berücksichtigung welcher Buchstabe vorkomme/nicht vorkommt.

$\begin{eqnarray*} 4 * 3^{n} \end{eqnarray*}$ die anzahl derjenigen, wo jeweils nur 1 buchstabe fehlt...und das ganze mal 4

$\begin{eqnarray*} 6 * 2^{n} \end{eqnarray*}$ die anzahl derjenigen, wo jeweils 2 buchstaben fehlen...und das ganze mal 6

$\begin{eqnarray*} 4 * 1^{n} = 4 \end{eqnarray*}$ die anzahl derjenigen, wo jeweils 3 buchstaben fehlen, die also nur aus einem buchstaben bestehen...und das ganze mal 4

wie rechne ich das jetzt?

24.09.2010, 17:45

Lord Pünktchen

Auf diesen Beitrag antworten »

RE: Inklusion/Exklusion: DNA Sequenzen
Die Einschluss- Ausschlussformel (Prinzip der Inklusion/Exklusion) verwendet gewisse Ereignisse bzw. Mengen.

Wie könnte man den nun die Menge

$\begin{eqnarray*} \left\{ (x_1,...,x_n)\in \{A,C,G,T\}^n | A,C,G,T \in (x_1,...,x_n) \right\} \end{eqnarray*}$

geeignet als Schnitt bzw. Vereinigung von möglichst einfach zu berechnenden Mengen/Ereignissen schreiben?

24.09.2010, 18:43

OVetS

Auf diesen Beitrag antworten »

das ist mir schon klar, ich weiß jetzt nur nicht, welche mengen ich abziehe und welche ich addiere...

so vllt...

$\begin{eqnarray*} 4^{n} - 4 * 3^{n} + 6 * 2^{n} + 4 \end{eqnarray*}$

kann mir das nochmal jemand erklären smile

24.09.2010, 18:47

René Gruber

Auf diesen Beitrag antworten »

Fast - aber bitte bis zum Schluss alternieren:

$\begin{eqnarray*} 4^n - 4 \cdot 3^n + 6 \cdot 2^n - 4 \end{eqnarray*}$

24.09.2010, 18:51

OVetS

Auf diesen Beitrag antworten »

und warum? kannst du das bitte nochmal erklären smile

24.09.2010, 18:55

René Gruber

Auf diesen Beitrag antworten »

RE: Inklusion/Exklusion: DNA Sequenzen
Wie "warum" ? Du hast es doch selbst perfekt erklärt:

Zitat:

Original von OVetS
Meine Ideen:
$\begin{eqnarray*} 4^{n} \end{eqnarray*}$ wäre doch die anzahl ohne berücksichtigung welcher Buchstabe vorkomme/nicht vorkommt.

$\begin{eqnarray*} 4 * 3^{n} \end{eqnarray*}$ die anzahl derjenigen, wo jeweils nur 1 buchstabe fehlt...und das ganze mal 4

$\begin{eqnarray*} 6 * 2^{n} \end{eqnarray*}$ die anzahl derjenigen, wo jeweils 2 buchstaben fehlen...und das ganze mal 6

$\begin{eqnarray*} 4 * 1^{n} = 4 \end{eqnarray*}$ die anzahl derjenigen, wo jeweils 3 buchstaben fehlen, die also nur aus einem buchstaben bestehen...und das ganze mal 4

Der Rest ist dann nur noch Einsetzen in die Siebformel.

An welcher Stelle klemmt es denn nun ganz genau? Ich will hier schließlich nicht die ganze Siebformel beweisen, das kannst du anderswo viel besser nachlesen.

24.09.2010, 18:55

OVetS

Auf diesen Beitrag antworten »

die siebformel! wie lautet die?

das ist der punkt den ich nicht verstehe

einfach nur - ... + ... - ... + ... - ... ?

24.09.2010, 19:07

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von OVetS
die siebformel! wie lautet die?

Lies selbst nach (z.B. Wikipedia).

Angewandt wird die Siebformel hier jedenfalls auf die 4 Mengen

$\begin{eqnarray*} A_1 \end{eqnarray*}$ ... Menge der Sequenzen der Länge $\begin{eqnarray*} n \end{eqnarray*}$ ohne jedes A
$\begin{eqnarray*} A_2 \end{eqnarray*}$ ... Menge der Sequenzen der Länge $\begin{eqnarray*} n \end{eqnarray*}$ ohne jedes C
$\begin{eqnarray*} A_3 \end{eqnarray*}$ ... Menge der Sequenzen der Länge $\begin{eqnarray*} n \end{eqnarray*}$ ohne jedes G
$\begin{eqnarray*} A_4 \end{eqnarray*}$ ... Menge der Sequenzen der Länge $\begin{eqnarray*} n \end{eqnarray*}$ ohne jedes T

alles Teilmengen der Gesamtmenge $\begin{eqnarray*} \Omega \end{eqnarray*}$ aller Sequenzen der Länge $\begin{eqnarray*} n \end{eqnarray*}$ .

Gesucht ist nun bei dir die Anzahl

$\begin{eqnarray*} \left| A_1^c \cap A_2^c \cap A_3^c \cap A_4^c \right| = \left| \left(A_1 \cup A_2 \cup A_3 \cup A_4 \right)^c \right| = \left| \Omega \right| - \left| A_1 \cup A_2 \cup A_3 \cup A_4 \right| \end{eqnarray*}$ ,

und zu eben jener letzten Vereinigungsgröße $\begin{eqnarray*} \left| A_1 \cup A_2 \cup A_3 \cup A_4 \right| \end{eqnarray*}$ kann dir die Siebformel Auskunft erteilen.

25.09.2010, 18:48

OVetS

Auf diesen Beitrag antworten »

ok danke....muss versuchen das jetzt irgendwie zu verstehen

Neue Frage »

Antworten »

Inklusion/Exklusion: DNA Sequenzen

Verwandte Themen