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.

do góry

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...

do góry

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

do góry

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-li
near-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.

do góry

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-li
near-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

do góry

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.

do góry

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

do góry

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ć.

do góry

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-slide
r-tools/master/corpus/afnetworking-human.sliders
jest
3e3d94f93828f5eeb11fc1218c3bc45399e9a66e:AFNetworkin
g/AFRestClient.h
5cf1028433228b20e7cf30a463353981809fcd0b:AFNetworkin
g/AFRestClient.h - 77 -2

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

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

do góry