Algoritme søges: clustering af distinkte sæt
Hej,Jeg søger en algoritme eller blot navnet på den. Algoritmen må da gerne være grådig, bare den er mere effektiv end n^2.
Mit problem er bioinformatisk (bare for at prale) og er sat følgende sammen:
Jeg har et stort antal gener, som hver kan være tilknyttet et eller flere pathways. Antallet af tilknyttet pathways per gen er stærkt varierende. Et pathway kan være repræsenteret i et eller flere gener; kun pathways der er repræsenteret i gensættet er medtaget. Gener og pathways er blot identificeret med et id.
Dvs., men pseudo matematisk notation:
[code]gene_1 = {path_a, path_c}
gene_2 = {path_a, path_b}
gene_3 = {path_d}
gene_4 = {path_c, path_e}
[/code]
eller opstilles som link matrix:
[code]
a b c d e
1 1 0 1 0 0
2 1 1 0 0 0
3 0 0 0 0 1
4 0 0 1 0 1
[/code]
Udfordringen er nu, at gruppere flest mulige gener sammen i færrest mulige grupper, således at en pathway kun er tilknyttet ét gen ad gangen. Ved ovenstående kan gene 1 og 3 grupperes sammen og 2 og 4 grupperes sammen.
Er der nogen idéer. Det skal implementeres i R.