Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #31439 > unrolled thread

Ktoś używał 1000genomes?

Back to article view | Back to pl.comp.programming

Contents

  Ktoś używał 1000genomes? Borneq <borneq@antyspam.hidden.pl> - 2018-02-05 01:11 +0100
    Re: Ktoś używał 1000genomes? Borneq <borneq@antyspam.hidden.pl> - 2018-02-05 01:28 +0100
      Re: Ktoś używał 1000genomes? "M.M." <mmarszik@gmail.com> - 2018-02-05 01:31 -0800
        Re: Ktoś używał 1000genomes? Diff Borneq <borneq@antyspam.hidden.pl> - 2018-02-05 13:53 +0100
          Re: Ktoś używał 1000genomes? Diff "M.M." <mmarszik@gmail.com> - 2018-02-05 09:13 -0800
            Re: Ktoś... Algorytmy Diff Borneq <borneq@antyspam.hidden.pl> - 2018-02-05 22:19 +0100
              Re: Ktoś... Algorytmy Diff "M.M." <mmarszik@gmail.com> - 2018-02-06 01:55 -0800
              Re: Ktoś... Algorytmy Diff Borneq <borneq@antyspam.hidden.pl> - 2018-02-09 11:09 +0100
                Re: Ktoś... Algorytmy Diff Borneq <borneq@antyspam.hidden.pl> - 2018-02-09 12:42 +0100

#31439 — Ktoś używał 1000genomes?

https://ftp-trace.ncbi.nih.gov/1000genomes/ftp/
				
Szukam jakiegoś genu w dwóch wersjach albo genotypu bakterii, wirusa, 
nie tyle z biologicznego punktu widzenia ale chciałem użyć tych danych 
do przetestowania standardowego algorytmu Diff Eugene Myersa 
(http://www.xmailserver.org/diff2.pdf) i jego wariantów.

[toc] | [next] | [standalone]

#31440

W dniu 05.02.2018 o 01:11, Borneq pisze:
> https://ftp-trace.ncbi.nih.gov/1000genomes/ftp/

Przyjrzałem się, nie tak łatwo, to cała ciekawa dziedzina wiedzy, pliki 
vcf, indeksy, markery...

[toc] | [prev] | [next] | [standalone]

#31441

On Monday, February 5, 2018 at 1:28:03 AM UTC+1, Borneq wrote:
> W dniu 05.02.2018 o 01:11, Borneq pisze:
> > https://ftp-trace.ncbi.nih.gov/1000genomes/ftp/
> 
> Przyjrzałem się, nie tak łatwo, to cała ciekawa dziedzina wiedzy, pliki 
> vcf, indeksy, markery...

Dziedzina wiedzy dziedziną wiedzy, ale porównania się robi i używa się
do tego analogicznych algorytmów jak do porównywania ciągów znaków.

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#31442 — Re: Ktoś używał 1000genomes? Diff

W dniu 05.02.2018 o 10:31, M.M. pisze:
> Dziedzina wiedzy dziedziną wiedzy, ale porównania się robi i używa się
> do tego analogicznych algorytmów jak do porównywania ciągów znaków.

Czytałem o algorytmie Myersa wspaniale wytłumaczonym na blogu jcoglan.
Znajduje maksymalny wspólny podciąg, ale rozwiązań może być wiele. W 
podstawowej wersji ma tę miłą właściwość że gromadzi inserty i delety 
razem. Jednak wersja profesjonalna, używająca liniowego a nie 
kwadratowego miejsca pamięci, nie ma tej właściwości.
Przykład: 
https://blog.jcoglan.com/2017/03/22/myers-diff-in-linear-space-theory/

Jak można by to poprawić? Może najpierw rekurencyjnie dzielić na bloki, 
ale gdy blok nie przekracza 50 wierszy, robić wersję standardową?
Poza tym, implementacja Butlera z CodeProject dla liniowego:
782104906830590
683059078210490
daje lepsze rezultaty niż można by się spodziewać.

Git ma jeszcze możliwość opcji --patience, która poprawia, jednak 
wyszukując unikalne wiersze - nie nadaje się np. do genomu.

[toc] | [prev] | [next] | [standalone]

#31443 — Re: Ktoś używał 1000genomes? Diff

On Monday, February 5, 2018 at 1:53:06 PM UTC+1, Borneq wrote:
> W dniu 05.02.2018 o 10:31, M.M. pisze:
> > Dziedzina wiedzy dziedziną wiedzy, ale porównania się robi i używa się
> > do tego analogicznych algorytmów jak do porównywania ciągów znaków.
> 
> Czytałem o algorytmie Myersa wspaniale wytłumaczonym na blogu jcoglan.
> Znajduje maksymalny wspólny podciąg, ale rozwiązań może być wiele. W 
> podstawowej wersji ma tę miłą właściwość że gromadzi inserty i delety 
> razem. Jednak wersja profesjonalna, używająca liniowego a nie 
> kwadratowego miejsca pamięci, nie ma tej właściwości.
> Przykład: 
> https://blog.jcoglan.com/2017/03/22/myers-diff-in-linear-space-theory/
> 
> Jak można by to poprawić? Może najpierw rekurencyjnie dzielić na bloki, 
> ale gdy blok nie przekracza 50 wierszy, robić wersję standardową?
> Poza tym, implementacja Butlera z CodeProject dla liniowego:
> 782104906830590
> 683059078210490
> daje lepsze rezultaty niż można by się spodziewać.
> 
> Git ma jeszcze możliwość opcji --patience, która poprawia, jednak 
> wyszukując unikalne wiersze - nie nadaje się np. do genomu.

Z tego co pobieżnie kiedyś dawno temu przeglądałem, to temat jest
niebagatelny, ponieważ istnieje wiele heurystyk. Poszczególne 
heurystyki różnie podnoszą skuteczność pamięciową i/albo obliczeniową
w zależności od danych; głównie chodzi o to, na ile porównywane
podciągi są podobne. Przy złożoności obliczeniowej M*N
ciężko policzyć dla choćby miliona genów, nie wspominając o 
pamięciowej.

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#31444 — Re: Ktoś... Algorytmy Diff

W dniu 05.02.2018 o 18:13, M.M. pisze:
> podciągi są podobne. Przy złożoności obliczeniowej M*N
> ciężko policzyć dla choćby miliona genów, nie wspominając o
> pamięciowej.

Zamiast na genomie, może przetestuję tak:
wezmę spory plik w c. Zrobię różne modyfikacje przez usuwanie 
pojedynczych wierszy i grup wierszy, oraz przenoszenia bloków kodu. Nie 
muszę zapisywać plików, będę działał na ich kodach crc32 (choć git diff 
używa kodów 64 bitowych) i wtedy zobaczę jak prędkość w dość realnych 
przypadkach.

[toc] | [prev] | [next] | [standalone]

#31445 — Re: Ktoś... Algorytmy Diff

On Monday, February 5, 2018 at 10:19:25 PM UTC+1, Borneq wrote:
> W dniu 05.02.2018 o 18:13, M.M. pisze:
> > podciągi są podobne. Przy złożoności obliczeniowej M*N
> > ciężko policzyć dla choćby miliona genów, nie wspominając o
> > pamięciowej.
> 
> Zamiast na genomie, może przetestuję tak:
> wezmę spory plik w c. Zrobię różne modyfikacje przez usuwanie 
> pojedynczych wierszy i grup wierszy, oraz przenoszenia bloków kodu. Nie 
> muszę zapisywać plików, będę działał na ich kodach crc32 (choć git diff 
> używa kodów 64 bitowych) i wtedy zobaczę jak prędkość w dość realnych 
> przypadkach.

Ja używam diff do porównywania archiwów. Archiwum zawiera tysiące
plików i ma łączny rozmiar wielu gigabajtów. Działa błyskawicznie.

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#31447 — Re: Ktoś... Algorytmy Diff

W dniu 05.02.2018 o 22:19, Borneq pisze:
> Zamiast na genomie, może przetestuję tak:
> wezmę spory plik w c. Zrobię różne modyfikacje przez usuwanie 

Znalazłem coś ciekawego:
https://github.com/mhagger/diff-slider-tools
Heurystyki porównywania i korpus na którym można testować.

[toc] | [prev] | [next] | [standalone]

#31448 — Re: Ktoś... Algorytmy Diff

W dniu 09.02.2018 o 11:09, Borneq pisze:
> Heurystyki porównywania i korpus na którym można testować.

Czy ten korpus nie ma za mało danych? jeszcze będę musiał się przyjrzeć, bo
https://raw.githubusercontent.com/mhagger/diff-slider-tools/master/corpus/afnetworking-human.sliders
jest
3e3d94f93828f5eeb11fc1218c3bc45399e9a66e:AFNetworking/AFRestClient.h 
5cf1028433228b20e7cf30a463353981809fcd0b:AFNetworking/AFRestClient.h - 77 -2

czyli dwa pliki
https://raw.githubusercontent.com/AFNetworking/AFNetworking/3e3d94f93828f5eeb11fc1218c3bc45399e9a66e/AFNetworking/AFRestClient.h
https://raw.githubusercontent.com/AFNetworking/AFNetworking/5cf1028433228b20e7cf30a463353981809fcd0b/AFNetworking/AFRestClient.h

kilka różnic i tylko dwie liczby: "- 77 -2"

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web