[c++] omzetten van char naar binair getal

Pagina: 1
Acties:
  • 1.347 views sinds 30-01-2008
  • Reageer

Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
Ik wil een soort hash table maken voor een dna sequentie. De sequentie is een (lange) string van vier verschillende letters (A, C, T, G). Ik wil de sequentie in stukken van 4 letters lang knippen en iedere mogelijke combinatie van vier letters een unieke id geven, dat zijn 4^4 mogelijkheden.

Voorbeeld:
AAAAATTCGTGA

AAAA
AAAA
AAAT
AATT
etc

Om voor iedere mogelijke combinatie van letters wilde ik eerst de verschillende letters omzetten naar 1'en en 0'en.

00 = A
01 = C
10 = G
11 = T

TCGA zou dan worden:

(in binary): 11011000
(in dec): 216

Ik ben nu zover dat ik de letter inlees en deze omzet naar 1'en en 0'en. Maar dit zijn chars en geen binaire getallen (zie code). Hoe zorg ik ervoor dat ik een A omzet naar binair 00 en een T naar binair 11??? Hieronder staat mijn code.

code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
char* a = "00";
char* c = "01";
char* g = "10";
char* t = "11";

...

for(i=0; i< size-matchLength; i++)
{
    input.seekg(i,ios::beg);            
    input.read(buffer, matchLength);    
    cout << i << "\t" << buffer << "\t";

    char* bin;
    bin = new char[4];

    for(j=0; j < matchLength; j++)
    {
        switch (buffer[j])
        { 
            case 'a' :
            {
                cout << a << "\t";
                strcat(bin, a);
                break;
            }
            case 'c' :
            {
                cout << c << "\t";
                strcat(bin, c);
                break;
            }
                        .....
        }
    }
    cout << endl << bin << endl;
    delete[] bin;


Bin is hierbij die gewoon een char van 1'en en 0'en en ik wil dus dat dit een binair getal is ipv een char.

[ Voor 10% gewijzigd door Verwijderd op 23-01-2006 16:27 ]


Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 28-07 23:58

.oisyn

Moderator Devschuur®

Demotivational Speaker

En je vraag is...?
.edit: ah ik zie 'm al, hij zat een beetje verstopt.

Dat lijkt me toch simpel? Je weet blijkbaar al hoe je binair naar decimaal om kunt zetten, dus dan kun je ipv de strings toch gewoon de decimale waarden pakken? Oftewel, 0 t/m 3.

Die waarden stop je vervolgens op de goede plek mbv de << (shift-left) en | (or) operators.

[ Voor 103% gewijzigd door .oisyn op 23-01-2006 16:22 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • TweakerNummer
  • Registratie: September 2001
  • Niet online
Mij lijkt me dat "Hoe zorg ik ervoor dat ik een A omzet naar binair 00 en een T naar binair 11" zijn vraag is (die zin had best wel eens mogen eindigen met een vraagteken overigens).

Alles is in princiepe binair in een machine. Er is geen speciale binaire primitieve in C (dacht ik). Zoals de admin al zei (na zijn editing), gewoon lekker het getal als decimale var opslaan, en dan als binair uitprinten. We weten niet echt wat je wilt gaan doen met de "binaire" waardes.

Je kan een nieuwe type/object maken, die dan stieken een int is (en dan zal je nog zelf de operaties op je nieuwe type moeten definieren). Maar sneller is gewoon met strings te werken en dan, als je de string wilt printen, door hele string heen te lopen (1 char per keer) en dan een 00, 01, 10, of 11 te printen afhankelijk van de char die net ingelezen is.

[ Voor 61% gewijzigd door TweakerNummer op 23-01-2006 16:29 ]


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
oh sorry was inderdaad niet helemaal duidelijk :) Ik lees nu het bestand in en verander de letters in 1'en 0'en dmv de switch-case. Maar zijn dus chars terwijl dit binaire getallen moeten zijn. Dus dit zijn nu chars

code:
1
2
3
4
char* a = "00";
char* c = "01";
char* g = "10";
char* t = "11";


en ik wil dat dit binaire getallen worden. Dus mijn vraag is hoe doe ik dat? Dus hoe zorg ik ervoor als je de volgende combinatie hebt AATG dat het resultaat een binair getal is (in dit geval 00 00 11 10) en geen string zoals nu in mijn code het geval is.

Acties:
  • 0 Henk 'm!

  • Obliterator
  • Registratie: November 2000
  • Laatst online: 08-07 15:12
In plaats van die char *a neem je int a, en die vul je met
code:
1
2
int a = 0x00;
int c = 0x01;


Dan inplaats van de string aan elkaar te plakken shift je de bin variabele (die ook int is geworden) naar links, en tel je de juiste variabele (a,c,g,t) erbijop.

Acties:
  • 0 Henk 'm!

  • Dido
  • Registratie: Maart 2002
  • Laatst online: 15:14

Dido

heforshe

Is dit geen omslachtige oplossing?

Je hebt 256 mogelijkheden. Als je je vier posities omzet naar integers 0, 1, 2 en 3 voor resp a, c, g, en t, dan bereken je je uiteindelijke waarde als p1*64 + p2 * 16 + p3 * 4 + p4. Dat geeft je alle waardes van 0 tot en met 255, die alle 256 mogelijke combinaties uniek definieren, en hoef je niet via binair te rekenen (dat doe je eigenlijk stiekem een beetje, hoewel dat eigenlijk quaternair is).

a=0, c=1, g=2, t=3
N=p1*64 + p2 * 16 + p3 * 4 + p4
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
p1  p2  p3  p4  N
0   0   0   0   0
0   0   0   1   1
0   0   0   2   2
0   0   0   3   3
0   0   1   0   4
0   0   1   1   5
0   0   1   2   6
0   0   1   3   7
0   0   2   0   8
0   0   2   1   9
0   0   2   2   10
0   0   2   3   11
0   0   3   0   12
0   0   3   1   13
0   0   3   2   14
0   0   3   3   15

enzovoort?

[ Voor 26% gewijzigd door Dido op 23-01-2006 16:33 ]

Wat betekent mijn avatar?


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
TweakerNummer schreef op maandag 23 januari 2006 @ 16:21:
[...]
We weten niet echt wat je wilt gaan doen met de "binaire" waardes.
Ik wil een sequentie inlezen (200.000.000 letters) en deze in stukken vier hakken. Er zijn dan 4^4 mogelijke combinaties van letters. Ik wil iedere combinatie een uniek id geven als ik de file inlees.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 25-07 23:41
Er zijn geen binaire of decimale getallen; er zijn alleen getallen. Het getal 'drie' is net zo goed drie als je 3 of 310 schrijft als 112. Je kunt in je programmacode dus gewoon de getallen 0, 1, 2 en 3 gebruiken.

In het geheugen worden getallen meestal binair (d.w.z. in basis 2) gerepresenteerd met (minimaal) 8 bits voor een unsigned char:
0: 000000002,
1: 000000012,
2: 000000102,
3: 000000112.
Wat jij natuuurlijk wil is meer dan alleen die laagste paar bits gebruiken en dat kan inderdaad door met bits te schuiven en bitsgewijs te combineren. Bijvoorbeeld (1<<6)|(0<<4)|(2<<2)(3<<0) = 01.00.10.112 (puntjes voor de duidelijkheid toegevoegd). Hoewel je er een andere betekenis aan geeft in je programma, is dit nog steeds de binaire representatie van het getal 75.
Verwijderd schreef op maandag 23 januari 2006 @ 16:33:
Ik wil een sequentie inlezen (200.000.000 letters) en deze in stukken vier hakken. Er zijn dan 4^4 mogelijke combinaties van letters. Ik wil iedere combinatie een uniek id geven als ik de file inlees.
Misschien handig om aan te geven waar het mis gaat? Op basis van deze uitleg zou ik zeggen "goed plan - doe het gewoon!" ;) maar blijkbaar loop je ergens tegenaan.

[ Voor 29% gewijzigd door Soultaker op 23-01-2006 16:35 ]


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
Soultaker schreef op maandag 23 januari 2006 @ 16:33:
Misschien handig om aan te geven waar het mis gaat? Op basis van deze uitleg zou ik zeggen "goed plan - doe het gewoon!" ;) maar blijkbaar loop je ergens tegenaan.
Waar ik tegenaan loop? Ik zet het nu om naar een string van 1'en en 0'en ipv dat het een getal is.

Acties:
  • 0 Henk 'm!

  • Dido
  • Registratie: Maart 2002
  • Laatst online: 15:14

Dido

heforshe

En als je mijn "quaternaire methode" gebruikt?

Wat betekent mijn avatar?


Acties:
  • 0 Henk 'm!

  • TweakerNummer
  • Registratie: September 2001
  • Niet online
Verwijderd schreef op maandag 23 januari 2006 @ 16:47:
[...]


Waar ik tegenaan loop? Ik zet het nu om naar een string van 1'en en 0'en ipv dat het een getal is.
Je hebt dus 4 * 2 = 8 string getallen.
Het decimale nummer =
1e char van de string (die eerst omzetten naar een int 0 of int 1) * 128 +
2e char * 64 +
3e char * 32 +
4e char * 16 +
5e char * 8 +
6e char * 4 +
7e char * 2 +
8e char * 1

omzetten van char -> 0 of 1 is gewoon een vergelijking (if char == ascii_waarde_0 dan decimal = 0)

Het kan vast wel sneller maar dat is denk ik wat je dan wilt.

Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
Dido schreef op maandag 23 januari 2006 @ 16:49:
En als je mijn "quaternaire methode" gebruikt?
Ik ben dat nu aan het proberen. Maar dat is wel een mooie oplossing. Was er zelf niet opgekomen. Wil het liefst beide manieren werkend hebben om te kijken wat sneller is en hoeveel dat scheelt :)

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
In princiepe heeft soultaker ( en anderen daarboven ) het antwoord al gegeven. Voor een letter heb je 2 bits nodig om hem op te slaan. Als je een data type gebruikt waar je 8 bits tot je beschikking hebt kun je dus 4 dna char's oplaan in dat datatype.

wat je dan simpel gezegd doet is is een dna char omzetten in het goede getal ( 0, 1, 2 of 3 ) en opschuiven naar de juiste positie. De volgende stap is dat je dat met de volgende dna char ook doet en deze OR't met de uitkomt van de vorige berekening. Op deze manier kan je 4 dna char's opslaan in een data type van 8 bits.

[ Voor 3% gewijzigd door Woy op 23-01-2006 16:56 ]

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • schoene
  • Registratie: Maart 2003
  • Laatst online: 08:58
rwb schreef op maandag 23 januari 2006 @ 16:55:
wat je dan simpel gezegd doet is is een dna char omzetten in het goede getal ( 0, 1, 2 of 3 ) en opschuiven naar de juiste positie. De volgende stap is dat je dat met de volgende dna char ook doet en deze OR't met de uitkomt van de vorige berekening. Op deze manier kan je 4 dna char's opslaan in een data type van 8 bits.
maar als je aantal dna char's geen veelvoud van 4 is, zit je met problemen. Dus volgens mij heb je 3 bits nodig per dna char. En dan is het misschien beter om er 4 bits voor te gebruiken. en slechts 4 van de 16 mogelijkheden bevatten effectief een dna char.
bvb: 1000, 0100, 0010 en 0001. Als je een oneven aantal dna-chars hebt, dan eindigt je laatste byte bvb op 0000

Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 28-07 23:58

.oisyn

Moderator Devschuur®

Demotivational Speaker

schoene schreef op maandag 23 januari 2006 @ 17:42:

maar als je aantal dna char's geen veelvoud van 4 is, zit je met problemen.
Ik zie geen probleem, je moet uiteraard wel vermelden hoeveel dna chars je in totaal hebt.

Je kunt evt. ook een vector<bool> gebruiken, dan heb je een dynamische container waarin je individuele bits op kunt slaan.

[ Voor 21% gewijzigd door .oisyn op 23-01-2006 17:54 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
schoene schreef op maandag 23 januari 2006 @ 17:42:
[...]


maar als je aantal dna char's geen veelvoud van 4 is, zit je met problemen. Dus volgens mij heb je 3 bits nodig per dna char. En dan is het misschien beter om er 4 bits voor te gebruiken. en slechts 4 van de 16 mogelijkheden bevatten effectief een dna char.
bvb: 1000, 0100, 0010 en 0001. Als je een oneven aantal dna-chars hebt, dan eindigt je laatste byte bvb op 0000
Maar het gaat volgens de Topic start over 4 verschillende mogenlijkheden. Ik denk dat er bij DNA niet opeens een extra mogenlijkheid bij komt. Dus kan je het perfect af met 2 bits.

Als je bedoelt dat je mischien wat bits over hebt als je bijvoorbeeld 6 dna char's wilt representeren dan heb je gelijk maar datzelfde probleem heb je als je 4 bits gebruikt. Je kan beter gewoon bijhouden hoeveel chars je hebt opgeslagen.

edit:
grrr .oisyn moet het weer snel even eerder in een regel typen :P

[ Voor 5% gewijzigd door Woy op 23-01-2006 17:53 ]

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 18-06 11:36
Yep, en die heeft dan ook nog eens de betere oplossing. :P
C++:
1
case 'a': pushback(0); pushback(0); break;

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

  • Zoijar
  • Registratie: September 2001
  • Niet online

Zoijar

Because he doesn't row...

behalve dat vector<bool> evil is ;)

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
MSalters schreef op maandag 23 januari 2006 @ 21:03:
Yep, en die heeft dan ook nog eens de betere oplossing. :P
C++:
1
case 'a': pushback(0); pushback(0); break;
Ja maar dat edite hij er later bij dat is niet eerlijk :P. Maar daarbij vraag ik me wel af hoe hij een bool intern opslaat. Zou hij het echt zo optimaliseren dat hij 8 bools in een byte stopt??? Als dat niet het geval is dan heb je nog steeds hetzelfde geheugen probleem als ze gewoon in een char stoppen.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 28-07 23:58

.oisyn

Moderator Devschuur®

Demotivational Speaker

Ja, kijk maar :)

En ach, ik ben het er mee eens dat ze het beter in een soort dynamische variant van std::bitset hadden kunnen gieten, maar dat doet niets af aan het feit dat vector gewoon een nuttige klasse is en in vrijwel alle gangbare implementaties wel op één of andere manier wel ondersteund wordt. Desnoods doe je een typedef naar bit_vector oid, om verwarring te voorkomen.

.edit: oh, ik lees net dat er een consensus is bereikt in april 2005 hierover en dat ie deprecated is. Dat verandert de zaak natuurlijk enigszins :)

[ Voor 83% gewijzigd door .oisyn op 24-01-2006 00:27 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
Dan kan het idd slim zijn om het op die manier op te lossen. Had er eigenlijk niet opgekomen dat het "gewoon" een specialization zou zijn van een Vector, maarja ik ben dan ook niet zo vaak met c++ en templates bezig.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
MSalters schreef op maandag 23 januari 2006 @ 21:03:
Yep, en die heeft dan ook nog eens de betere oplossing. :P
C++:
1
case 'a': pushback(0); pushback(0); break;
Ik heb het nou op deze manier gedaan. Ik heb nu een vector met daarin 1'en en 0'en. Maar hoe zorg ik nou dat dit een decimal wordt? Dit is mijn output:

0 attc theVector [ 0, 0, 1, 1, 1, 1, 0, 1 ]
1 ttcg theVector [ 1, 1, 1, 1, 0, 1, 1, 0 ]

Acties:
  • 0 Henk 'm!

  • Zoijar
  • Registratie: September 2001
  • Niet online

Zoijar

Because he doesn't row...

.oisyn schreef op dinsdag 24 januari 2006 @ 00:02:
.edit: oh, ik lees net dat er een consensus is bereikt in april 2005 hierover en dat ie deprecated is. Dat verandert de zaak natuurlijk enigszins :)
vector<bool> is geen STL container in de zin dat het template argument, bool, niet het juiste model volgt. bool is namelijk niet dereferencable, en dat zorgt voor een zooi problemen. Er is idd wel een soort van halve oplossing met een proxy, maar dat breekt alsnog de STL aannames... dereference is niet heel snel zoals je mag verwachten, en je kan nog steeds niet een pointer-to-bool verkrijgen op wat voor manier dan ook. Boost bevat een dynamic_bitset overigens.

Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 28-07 23:58

.oisyn

Moderator Devschuur®

Demotivational Speaker

Zoijar schreef op dinsdag 24 januari 2006 @ 10:39:
[...]

vector is geen STL container in de zin dat het template argument, bool, niet het juiste model volgt. bool is namelijk niet dereferencable, en dat zorgt voor een zooi problemen.
Dat snap ik. Wat ik zeg is dat het verder wél een werkende klasse is. Hij is evil omdat het niet voldoet aan de standard requirements voor containers, en dat het zich al helemaal niet als een standaard vector gedraagd. Als je dat weet en daar rekening mee houdt, dan kun je 'm dus prima gebruiken.

Wat jij aandraagt is een argument om 'm überhaupt niet in de standaard op te nemen; dat is helaas al gebeurd. Een reden om 'm nu niet te gebruiken is niet door al die punten die jij noemt, maar dat het nogal likely is dat de specialization weer uit de standaard verwijderd wordt, waardoor huidige code breekt.

[ Voor 21% gewijzigd door .oisyn op 24-01-2006 11:09 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • Zoijar
  • Registratie: September 2001
  • Niet online

Zoijar

Because he doesn't row...

.oisyn schreef op dinsdag 24 januari 2006 @ 11:02:
Dat snap ik. Wat ik zeg is dat het verder wél een werkende klasse is. Hij is evil omdat het niet voldoet aan de standard requirements voor containers, en dat het zich al helemaal niet als een standaard vector gedraagd. Als je dat weet en daar rekening mee houdt, dan kun je 'm dus prima gebruiken.

Wat jij aandraagt is een argument om 'm überhaupt niet in de standaard op te nemen; dat is helaas al gebeurd. Een reden om 'm nu niet te gebruiken is niet door al die punten die jij noemt, maar dat het nogal likely is dat de specialization weer uit de standaard verwijderd wordt, waardoor huidige code breekt.
Ja, ok. Het was ook even ter verduidelijking aan de anderen over het 'waarom', niet specifiek tegen jou eigenlijk (ik weet dat jij stof wel kent hehe)

Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 28-07 23:58

.oisyn

Moderator Devschuur®

Demotivational Speaker

Right, stom van me :P

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 18-06 11:36
.oisyn schreef op dinsdag 24 januari 2006 @ 11:02:
Een reden om 'm nu niet te gebruiken is niet door al die punten die jij noemt, maar dat het nogal likely is dat de specialization weer uit de standaard verwijderd wordt, waardoor huidige code breekt.
Code breekt niet, het geheugengebruik zou omhoog schieten. Maar als dat gebeurt is het vrijwel zeker een kwestie van replace(vector<bool>, vector_bool). Ik geloof niet dat er veel template code zal zijn die vector<T> gebruikt en dan de <bool> specialisatie verwacht.

(En het breekt niks - alleen het geheugengebruik gaat naar 800%)

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 18-06 11:36
Verwijderd schreef op dinsdag 24 januari 2006 @ 10:24:
[...]
Ik heb het nou op deze manier gedaan. Ik heb nu een vector met daarin 1'en en 0'en. Maar hoe zorg ik nou dat dit een decimal wordt? Dit is mijn output:

0 attc theVector [ 0, 0, 1, 1, 1, 1, 0, 1 ]
1 ttcg theVector [ 1, 1, 1, 1, 0, 1, 1, 0 ]
Nou moet 'ie opeens naar decimaal? In je TS ging het nog om binair, en dat heb je nu duidelijk.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 28-07 23:58

.oisyn

Moderator Devschuur®

Demotivational Speaker

MSalters schreef op dinsdag 24 januari 2006 @ 20:12:
[...]
Code breekt niet, het geheugengebruik zou omhoog schieten.
C++:
1
2
3
4
5
6
7
void func()
{
    std::vector<bool> v(32, false);
    v.flip();
    v[0].flip();
    // v representeert nu de signed int -1
}

Dat lukt toch echt niet met een unspecialized vector :). En dát is de reden waarom mensen als Sutter ervoor pleiten om 'm wel te houden, maar dan onder een andere naam: compatibility met oude code.

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • paulh
  • Registratie: Juli 1999
  • Laatst online: 21-07 21:10
Waarom schrijf je die characters (A, C, T, G) niet gewoon op die manier weg in een bestand en gebruik je daarna gewoon een compressie library. Zal vast ook wel aardig compact worden aangezien je maar 4 characters gebruikt.

[ZwareMetalen.com] - [Kom in aktie tegen de CO2 maffia]


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
MSalters schreef op dinsdag 24 januari 2006 @ 20:13:
[...]

Nou moet 'ie opeens naar decimaal? In je TS ging het nog om binair, en dat heb je nu duidelijk.
Ik wil voor iedere mogelijke combinatie van vier letters een uniek id (getal) krijgen.

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
Verwijderd schreef op woensdag 25 januari 2006 @ 09:21:
[...]


Ik wil voor iedere mogelijke combinatie van vier letters een uniek id (getal) krijgen.
Dan zul je het toch zoals eerder gezegd in een ander datatype moeten doen. Je hebt 2 bits per dna char nodig dus zul je een 8 bits datatype nodig hebben.

aangezien je dus 8 bits hebt is het ook makkelijk om alle mogenlijkheden te generenen als je dat zou willen

0 = 00 00 00 00 = A A A A
1 = 00 00 00 01 = A A A C
2 = 00 00 00 10 = A A A G
enz....

de getallen 0 ... 255 zijn dan alle mogenlijkheden die er zijn.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • paulh
  • Registratie: Juli 1999
  • Laatst online: 21-07 21:10
Is er wel rekening gehouden met het feit dat de lengte van dna-sequence misschien geen veelvoud van 4 is? Als je geen header opneemt in je bestand waar je zaken als lengte en dergelijke opneemt dan kom je zwaar in de problemen in de laatste byte van je bestand.

[ZwareMetalen.com] - [Kom in aktie tegen de CO2 maffia]


Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 18-06 11:36
.oisyn schreef op dinsdag 24 januari 2006 @ 20:31:
[...]
C++:
1
2
3
4
5
6
7
void func()
{
    std::vector<bool> v(32, false);
    v.flip();
    v[0].flip();
    // v representeert nu de signed int -1
}

Dat lukt toch echt niet met een unspecialized vector :).
Oh, ik dacht dat je alleen de geheugenoptimalisatie bedoelde die eruit zou gaan. Dat is namelijk de enige reden dat vector<bool> geen STL Container is. flip() is niet in strijd met het Container concept.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 18-06 11:36
Verwijderd schreef op woensdag 25 januari 2006 @ 09:21:
[...]
Ik wil voor iedere mogelijke combinatie van vier letters een uniek id (getal) krijgen.
Dat heb je al - dat zijn de 8 opeenvolgende bits van je vector<bool>. In een computer zijn getallen nou eenmaal niets anders dan opeenvolgende bits.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
Dit is gelukt bedankt voor de hulp. Ik heb nu een lijst met id's voor alle verschillende mogelijkheden van 4 baseparen. Wat ik nu wil is de positie(s) in de DNA string koppelen aan het id nummer. Dus een soort tabel maken met Id en Positions-->

id		Positions in DNA string
1		3 53 345
2		6 24 456
etc


Hoe kan ik dit het beste doen? Ik zat te denken om een id naar een linked list te laten verwijzen.

[ Voor 8% gewijzigd door Verwijderd op 26-01-2006 09:32 ]


Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
Er zijn 256 verschillende id's mogenlijk ( Ik weet niet of ze allemaal bestaan maar daar ga ik even van uit ).

Ik zou dan een array met 256 lijsten maken. Dan moet je je DNA string doorlopen en voor elke 4 chars kijk je dan welk ID het is, dan voeg je in de bijbehorende lijst de positie in je DNA string toe.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
In dit voorbeeld heb ik 4 letters gebruikt, maar het kan ook zijn dat ik stukken van 8 letters neem --> 84 mogelijkheden. Of stel dat ik een nog groter stuk neem dan 8. Wordt het dan niet te veel. En hoe maak ik een array met lists? Kan je ook een array van vectoren maken?

[ Voor 11% gewijzigd door Verwijderd op 26-01-2006 13:27 ]


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 25-07 23:41
Als je willekeurige substrings wil kunnen vinden zou ik zeggen dat je het beste gelijk een suffix tree kunt bouwen; dat is niet voor niets een van de meest gebruikte datastructuren bij onderzoek naar DNA strings. Ik denk alleen dat de implementatie jouw pet te boven gaat (NOFI ;)), dus dat is alleen een optie als je bereid bent flink te investeren in je programmeerervaring en je kennis van datastructuren en algoritmen.

Als je echter substrings van een bepaalde lengte (4 of 8, zoals je noemt) wil vinden, is een lijst met referenties sowieso makkelijker. Overigens heb ik ook nog wel een andere suggestie voor je, die wellicht makkelijker te implementeren is maar ook minder efficient.

Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
Soultaker schreef op donderdag 26 januari 2006 @ 13:35:
Als je willekeurige substrings wil kunnen vinden zou ik zeggen dat je het beste gelijk een suffix tree kunt bouwen.
Klopt hier heb ik naar gekeken, maar dat was inderdaad erg complex. :)
Overigens heb ik ook nog wel een andere suggestie voor je, die wellicht makkelijker te implementeren is maar ook minder efficient.
Wat voor idee heb jij er dan over. De snelheid is niet het grootste probleem, omdat we een computing grid tot onze beschikking hebben hier :)

[ Voor 12% gewijzigd door Verwijderd op 26-01-2006 13:45 ]


Acties:
  • 0 Henk 'm!

  • netvor
  • Registratie: September 2000
  • Laatst online: 08-04-2024
Als je met hele grote ID's gaat werken (bijv. 16) dan wordt een lijst met referenties ondoenlijk. Je hebt dan een array van 4.294.967.296 pointers naar list<char*>; alleen de pointers nemen al 16 GB aan ruimte in!

Maar goed, voor strings van 8 tekens is een array nog wel te doen. Maar het lijkt me waarschijnlijk dat de meest van die list's gewoon leeg blijven, want wat is de kans dat je een willekeurige string van 8 tekens in een string van 200000 tekens tegenkomt?

In dat geval zou je naar een HashMap kunnen kijken. Gebruik het unieke ID (als 16 bits unsigned int) als key, en een list<char*> als value.

Met list<char*> bedoel ik natuurlijk een linkedlist (STL, of je eigen) van pointers naar de char in de source-array waar het geheel begint.

Computer Science: describing our world with boxes and arrows.


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 25-07 23:41
imp schreef op donderdag 26 januari 2006 @ 14:16:
Maar goed, voor strings van 8 tekens is een array nog wel te doen. Maar het lijkt me waarschijnlijk dat de meest van die list's gewoon leeg blijven, want wat is de kans dat je een willekeurige string van 8 tekens in een string van 200000 tekens tegenkomt?
Uitgaande van een uniforme 'random' distributie, is die kans (1 - (1 - 1/48)200000-8+1) ofwel ruim 95%. Slechts ~1 op de 20 lijsten zal dus leeg zijn. De vraag is of zo'n DNA string ook inderdaad aan die distributie voldoet; dat weet de TS vast beter dan ik. :P
In dat geval zou je naar een HashMap kunnen kijken. Gebruik het unieke ID (als 16 bits unsigned int) als key, en een list<char*> als value.
Als de keys al min of meer uniform gedistribueerd zijn over hun bereik, dan is een hash table gebruiken alleen maar zinloze overhead.
Verwijderd schreef op donderdag 26 januari 2006 @ 13:43:
Wat voor idee heb jij er dan over. De snelheid is niet het grootste probleem, omdat we een computing grid tot onze beschikking hebben hier :)
Uitgaande van een index van N-grams zoals hier besproken was, kun je zoeken op langere substrings door de zoekstring op te splitsen in (eventueel overlappende) N-grams en de lijsten met posities te mergen. Een voorbeeld; stel je hebt de string:
BBABAABABBAB

En je bouwt een trigram index (die mapt dus elke substring van drie lang op een lijst van posities waar die voorkomen):
• AAB: 5
• ABA: 3, 6
• ABB: 8
• BAA: 4
• BAB: 2, 7
• BBA: 1, 9
• BAB: 10
Strings van drie lang kun je direct opzoeken, maar langere strings kun je vinden door lijsten te combineren, vergelijkbaar met hoe een RDBMS join-operaties uitvoert. Merk op dat de lijsten gesorteerd zijn, wat het mergen veel efficiënter maakt.

Stel je noemt de trigram op positie p TG(p) (dus TG(0) --> BBA). Als je de string 'BAABAB' zoekt, dan wil je dus alle posities p vinden zo dat TG(p) = BAA én TG(p+3) = BAB. Je pakt dan de twee lijsten { 4 } en { 2, 7 } en vind de elementen x uit { 4 } en y uit { 2, 7 }, zo dat p = x en y = p + 3. In dit geval is dat dus p = x = 4 en y = p + 3 = 7. Voor langere strings gaat het net zo, behalve dat je natuurlijk vaker lijsten moet samenvoegen.

Voor strings die geen veelvoud van drie lang zijn, kun je gewoon strings laten overlappen. Zoeken op 'ABBA' is simpelweg zoeken op TG(p) = 'ABB' en TG(p+1) = 'BBA' (en dan vind je p=8).

Verder kun je nog wat trucs uithalen zoals steeds bij de kortste lijst beginnen met samenvoegen (er is namelijk geen enkele reden waarom je van links naar rechts zou moeten samenvoegen). In de praktijk werkt dit aardig mits je lijsten met N-grams niet al te lang zijn, maar dat kun je dus uitbalanseren door een grotere N te kiezen. (Voor het DNA-alfabet zijn 8-grams, dus substrings van 8 karakters, waarschijnlijk een veel betere keuze.)

Voor het geval het merge-algoritme niet helemaal duidelijk is, een kort voorbeeld:
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> merge(const vector<int> &a, const vector<int> &b, int diff)
{
  vector<int>::const_iterator i = a.begin(), j = b.begin();
  vector<int> c;
  while(i != a.end() && j != b.end())
  {
    int d = *i - *j + diff;
    if(d < 0)
      ++i;
    else
    if(d > 0)
      ++j;
    else
    {
      /* d == 0 */
      c.push_back(*i);
      ++i; ++j;
    }
  }
  return c;
}

Code is verder niet getest; merge({4}, {2,7}, 3) levert als het goed is {4} op, zoals in het voorbeeld. Overigens kan de code voor langere lijsten nog efficiënter d.m.v. een binary search, maar dat heb ik maar achterwege gelaten.

[ Voor 16% gewijzigd door Soultaker op 26-01-2006 15:07 ]


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
Jij zit alweer een stap verder, is wel een goed idee trouwens :) . Ik zit voorlopig nog vast met het opslaan van de posities. Ik heb nu een vector met alle id's. Maar nu moet ik de id's nog koppelen aan de posities. Ik weet wel ongeveer hoe is dit wil doen, maar niet hoe ik dit in c++ moet uitvoeren.

Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 18-06 11:36
rwb schreef op donderdag 26 januari 2006 @ 10:59:
Er zijn 256 verschillende id's mogenlijk ( Ik weet niet of ze allemaal bestaan maar daar ga ik even van uit ).

Ik zou dan een array met 256 lijsten maken. Dan moet je je DNA string doorlopen en voor elke 4 chars kijk je dan welk ID het is, dan voeg je in de bijbehorende lijst de positie in je DNA string toe.
Jammer, maar helaas. Dat werkt niet voor sub-byte shifts. ACTG komt ook voor in AACT GAAA. Dat is ook niet erg. De STL heeft een std::search.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
MSalters schreef op donderdag 26 januari 2006 @ 21:20:
[...]

Jammer, maar helaas. Dat werkt niet voor sub-byte shifts. ACTG komt ook voor in AACT GAAA. Dat is ook niet erg. De STL heeft een std::search.
Daar heb je gelijk in. Ik heb dan ook geen flauw benul hoe en wat er precies met de DNA string gedaan moet worden. Probeer enkel simpele oplossingen aan te dragen. Maar blijkbaar wil de topic starter toch wat complexere dingen doen dan ik bedacht had.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 25-07 23:41
Blijkbaar wil 'ie er in zoeken; dan moet je er dus een index voor bouwen, en dan is het waarschijnlijk ook niet zinnig meer om de string te comprimeren door vier karakters in een byte te proppen. De index is namelijk toch veel groter.

Het is voor mij ook gissen wat het doel is, maar ik zou zeggen dat het het handigst is om de string gewoon met 1 byte per DNA karakter op te slaan (eventueel de A, C, G en T en vervangen door 0, 1, 2 en 3) zodat je je index gewoon kunt maken doorpointers naar elementen in je index te stoppen.

Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
Soultaker schreef op vrijdag 27 januari 2006 @ 17:11:
Blijkbaar wil 'ie er in zoeken; dan moet je er dus een index voor bouwen, en dan is het waarschijnlijk ook niet zinnig meer om de string te comprimeren door vier karakters in een byte te proppen. De index is namelijk toch veel groter.

Het is voor mij ook gissen wat het doel is, maar ik zou zeggen dat het het handigst is om de string gewoon met 1 byte per DNA karakter op te slaan (eventueel de A, C, G en T en vervangen door 0, 1, 2 en 3) zodat je je index gewoon kunt maken doorpointers naar elementen in je index te stoppen.
Wat ik wil is alle herhalende delen in een sequentie zoeken. Dus zoeken naar de posities van een combinatie van minimaal lengte N binnen een sequentie. Wat ik nu moet doen is een een 'tabel' maken waarbij iedere mogelijke combinatie met lengte N (van de 4 letter A,C,T,G) en de posities waar deze voorkomt. Ik hoop dat het zo iets duidelijker is.

Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 18-06 11:36
Tijd voor Knuth, denk ik. De triviale oplossing is de string aflopen, en bij elke index I kijken of er een stringmatch is tussen [I,I+N) en [J,J+N) met 0 >= J > I. Dat is uiteraard kwadratisch in de lengte. Een index maakt het inderdaad O(NlogN) wat zo goed als optimaal is.
Een index is overigens snel gebouwd, std::map is een geschikte logN container.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

Verwijderd

Verwijderd schreef op donderdag 26 januari 2006 @ 13:24:
In dit voorbeeld heb ik 4 letters gebruikt, maar het kan ook zijn dat ik stukken van 8 letters neem --> 84 mogelijkheden. Of stel dat ik een nog groter stuk neem dan 8. Wordt het dan niet te veel. En hoe maak ik een array met lists? Kan je ook een array van vectoren maken?
Bouw het eerst maar met blokken van 4 letters. Het ombouwen naar stukken van 8 letters lijkt mij dan triviaal.

Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
het indexeren lukt in principe wel, maar nu moet ik het in een container stoppen. Ik gebruik nu een 2d array van integers, maar dit is niet erg efficient. Ik bepaal eerst wel stukje van 4 letter het meest voorkomt in de sequence en aan de hand daarvan maak ik mijn 2d array. Dus als de combinatie AACG (id 6) 5 keer voorkomt krijgt mijn array de grootte van 256 x 5.

id	pos1	pos2	pos3	pos4	pos5
0	x	x	x		
..	
6	x	x	x	x	x	
.. 
256	x


x is hierbij de positie waar de combinatie gevonden is.

Een groot deel van de array blijft natuurlijk leeg, sommige combinaties zullen nl vrijwel nooit voorkomen. Op wat voor manier kan ik dit efficienter in het geheugen stoppen? Ik zat te denken aan een array van vectoren ofzo.

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
Een array van Vectoren lijkt me idd handig als alle id's van 0 t/m 256 voorkomen.

Als niet alle ID's voorkomen kan je eventueel nog een Vector ( of mischien een gesorteerde lijst ) maken waarin een struct zit dat het betreffende ID bijhoudt en daarnaast een Vector van de posities

[ Voor 10% gewijzigd door Woy op 02-02-2006 16:31 ]

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • 4VAlien
  • Registratie: November 2000
  • Laatst online: 24-06 09:47

4VAlien

Intarweb!

Je hebt niet gezegd wat nu precies het doel van je programma is. Als het inderdaad gaat om DNA vergelijken dan kan je reeds bestaande programma's beter gebruiken zoals Mummer, BLAST of FASTA. Ikzelf heb gekeken naar het Iterated Function System tijdens m'n stage en dit programma vergelijkt DNA zonder suffix trees.

http://130.89.161.66/~rene/ifs/stream-prune.c

Zolang je kleine sequences ( <10miljoen baseparen) wil vergelijkenis dit sneller dan suffix trees, maar schaalt helaas niet door naar chromosoom vs chromosoom nivo (150-200Mbasepair).

Dit is inderdaad in C geschreven maar dat zijn alle sequencers/matchers omdat de data waarmee je werkt simpel is en de algorithmes meestal ook nog wel te overzien zijn. Organisatie van je code in klasses biedt geen voordeel, het enigste wat je wil is throughput en een efficient algoritme.

[ Voor 26% gewijzigd door 4VAlien op 02-02-2006 17:39 . Reden: kleine toevoeging ]


Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 18-06 11:36
Verwijderd schreef op donderdag 02 februari 2006 @ 14:29:
het indexeren lukt in principe wel, maar nu moet ik het in een container stoppen. Ik gebruik nu een 2d array van integers, maar dit is niet erg efficient. Ik bepaal eerst wel stukje van 4 letter het meest voorkomt in de sequence en aan de hand daarvan maak ik mijn 2d array. Dus als de combinatie AACG (id 6) 5 keer voorkomt krijgt mijn array de grootte van 256 x 5.

id	pos1	pos2	pos3	pos4	pos5
0	x	x	x		
..	
6	x	x	x	x	x	
.. 
256	x


x is hierbij de positie waar de combinatie gevonden is.

Een groot deel van de array blijft natuurlijk leeg, sommige combinaties zullen nl vrijwel nooit voorkomen. Op wat voor manier kan ik dit efficienter in het geheugen stoppen? Ik zat te denken aan een array van vectoren ofzo.
toon volledige bericht
Een std::map van vectoren lijkt me het meest handig, met het oog op de toekomst.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
4VAlien schreef op donderdag 02 februari 2006 @ 17:36:
Je hebt niet gezegd wat nu precies het doel van je programma is. Als het inderdaad gaat om DNA vergelijken dan kan je reeds bestaande programma's beter gebruiken zoals Mummer, BLAST of FASTA.
Ik heb hier inderdaad naar gekeken. MUMmer leek mij erg goed, net zoals patternhunter, maar mijn 'begeleider' wil het zelf programmeren 8)7 Maar wat ik wil is alle repeats in het DNA vinden. Niet alleen de 100% matches, maar ook bijvoorbeeld 90%. Ik zal wel kijken naar jou code. Heel erg bedankt daarvoor!
MSalters schreef op donderdag 02 februari 2006 @ 20:01:
[...]
Een std::map van vectoren lijkt me het meest handig, met het oog op de toekomst.
Zou je een heel eenvoudig voorbeeld kunnen geven hoe dit moet? Ben nog niet echt bekend met c++.

Acties:
  • 0 Henk 'm!

  • 4VAlien
  • Registratie: November 2000
  • Laatst online: 24-06 09:47

4VAlien

Intarweb!

Okay het gaat dus om repeats detecteren. Je bent op de hoogte van Reputer ( http://bibiserv.techfak.uni-bielefeld.de/reputer/ )? En met wat voor datasets ben je van plan te gaan werken? Kleine waarschuwing, het maken van exacte matches is relatief eenvoudig, maar de wetenschap (statistiek) achter scoringsalgorithmes voor niet exacte matches is een vak op zich. Het maken van een mummer kloon die korte exacte matches aangeeft zal niet een onoverkomelijk probleem zijn, maar voor scoringsmechanismen kan je toch het beste afkijken bij Blast en Fasta (Met dank aan Pearson voor onderzoek).

Verder zou het ubercool zijn als je mijn methode http://mat018102.student....ifs/LB-1KNZW06revised.doc (staat nog wat meer zut in die dir) erin kan verwerken, we hadden wel vermoedens dat het juist voor repeats extra nuttig is omdat die zich in de IFS matrix op de diagonalen bevinden. Maar ja toen was m'n tijd op :(

Hier nog wat references uit mijn verslag die wel relevant zijn voor het geval je ook een eigen scoringsmechanisme wil pakken, vooral 12 is de moeite van het lezen waard:

8. Sun, Z. and Deogun, J.S. (2004). “Local Prediction Approach of Protein Classification using Probabilistic Suffix Trees” In Proc. Second Asia-Pacific Bioinformatics Conference (APBC2004), Dunedin, New Zealand. CRPIT, 29. Chen, Y.-P. P., Ed. ACS. 357-362.

Suffix trees for prediction. Predicts the probability that a protein belongs to a certain family by either significant regions or most conserved region. An effective way to extract motifs/domains.

9. M. Boden, J. Hawkins, “Improved access to Sequential Motifs: A note on the architectural bias of recurrent networks”, IEEE transactions on neural networks (March 2005), 16(2).

The bias of recurrent networks offers superior access to motifs compared to standard feedforward neural networks.

10. J. Buhler, “Efficient large-scale sequence comparison by locality-sensitive hashing”, Bioinformatics (2001), 17(5):419-428.

An alternative hashing method that can’t guarantee 100% sensitivity but is good at identifying weak similarities.

11. Vincens P, Buffat L, Andre C, Chevrolat JP, Boisvieux JF, Hazout S.,"A strategy for finding regions of similarity in complete genome sequences", Bioinformatics 1998;14(8):715-725.

Alternative graph / 2D-distance based method to identify similar regions.

12. Pearson, W. R. and Wood, T. C. (2001) Statistical significance in biological sequence comparison. In Handbook of Statistical Genetics, D. J. Balding, M. Bishop, and C. Cannings, ed. (London, UK: Wiley), pp. 39-65.

Importance of bit-scores and statistical significance of alignments.

[ Voor 2% gewijzigd door 4VAlien op 04-02-2006 17:03 . Reden: ninja edit ]

Pagina: 1