MaybeJustJames
commented
3 years ago Project links:
- https://en.wikipedia.org/wiki/Sequence_assembly#Greedy_algorithm
- https://www.ensembl.org/Homo_sapiens/Gene/Summary?db=core;g=ENSG00000139618;r=13:32315086-32400268
- https://en.wikipedia.org/wiki/Sequence_alignment#Dynamic_programming
- https://en.wikipedia.org/wiki/Backtracking
- https://youtu.be/We3YDTzNXEk
- https://www.python-course.eu/levenshtein_distance.php
- https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python
- https://www.cis.upenn.edu/~cis110/12su/hw/hw06/dynprog.shtml
- https://youtu.be/KASvlXYPCBI, https://youtu.be/sseqEefj6Gs, https://youtu.be/KO2UaG8eKEw
- https://data-science-sequencing.github.io/Win2018/lectures/lecture6/
- https://nbviewer.jupyter.org/github/cschin/Write_A_Genome_Assembler_With_IPython/blob/master/Write_An_Assembler.ipynb
- https://pythonforbiologists.com/a-terrible-genome-assembler-in-six-lines
- https://github.com/kywertheim/Greedy_shortest_common_superstring/blob/main/main.py
Given a set of sequence fragments, the object is to find a longer sequence that contains all the fragments.
Сalculate pairwise alignments of all fragments. Choose two fragments with the largest overlap. Merge chosen fragments. Repeat step 2 and 3 until only one fragment is left. The result need not be an optimal solution to the problem.