+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: project coding python (/thread-31559.html)
project coding python - marcel2807 - Dec-18-2020
Hello everyone,
It's my first time on a forum but also my last hope in not failing my programming class. I've tried ours but no results. Here you can find what's my project about. I did the point 1,3,4,5 and I have a big issue with the numbers 2,6 and 7. Here is what I have to do:
Reconstructing evolution of a virus is critical to understand how its genome mutates
over time or during a pandemic as well as how the relative infection rate and clinical
presentation may vary in function of these mutations. For example, in the context of
COVID19 pandemic, the reconstruction of SARS-COV2 evolution can be found at
https://nextstrain.org/ncov/global.
We may encode the genome of a virus as a string of length L over the alphabet
Σ={A,C,T,G}. For example, the following string is the incipit of the Zaire Ebola virus:
CGGACACACAAAAAGAAAGAAGAATTTTTAGGATCTTTTGTGTGCGAATAACTATGAGGAAGATTAATAA
whereas the following string is the incipit of Crimean-Congo hemorrhagic fever virus
TCTCAAAGAAACACGTGCCGCTTACGCCCACAGTGTTCTCTTGAGTGTTAGCAGAATGGAAAACAAGATC.
This project is about designing and developing algorithms to manipulate a set of viral
genomes and to reconstruct their evolution. In particular, you have to write a python
program that:
1. Reads from the provided file the list of viral genomes; (1pt)
2. For each pair of genomes, lists all of the longest common patterns of length at least
5. (1pt)
A common pattern is defined as a substring that is shared by a pair of virus. In the
example above, Ebola and Crimean-Congo hemorrhagic fever virus share the
substring AAAGAAA, which has length 7.
3. Computes the distance matrix between genome pairwise by using the algorithm
shown in Figure 1; (1pt)
4. Outputs the minimum spanning tree induced by the above distance matrix, in the
form of a list of edges, e.g.,
edge 1 edge 2
edge 3 edge 4
…
edge n-2 edge n-1
(1,5pt)
5. Outputs (as in point 4) the shortest path tree induced by the above matrix; (0.5pt)
7. Finds the unrooted binary tree T which minimizes the following formula
where lij is the length of the path in T between the genome i and the genome j. Is T
topologically equivalent to the tree computed in point 6? (4pt)
Suggestions:
1. If n as the number of input sequences, then the number of internal vertices of
an unrooted binary tree is 2n-2.
2. The number of binary trees grows according to the law (2n-5)!!=1x3x5x7x…
(2n-5) where n=|G|.
3. The unrooted binary trees can be enumerated by starting from a star-tree
encoded e.g., as
T = { (1,n+1), (2,n+1), (3,n+1) }
and by inserting recursively each of the remaining genomes in G in one of the
edges of T. For example Suppose that G={1,2,3,4}. Then, the three possible
unrooted binary trees are:
i. T = { (2,n+1), (3,n+1), (4,n+2), (1,n+2), (n+1,n+2) }
ii. T = { (1,n+1), (3,n+1), (4,n+2), (2,n+2), (n+1,n+2) }
iii. T = { (1,n+1), (2,n+1), (4,n+2), (3,n+2), (n+1,n+2) }
As you can see, the insertion operation selects one vertex in G, say k, selects
one edge of T, say (u,v), removes (u,v) from T, and appends three new edges
in T, namely
iv. the edge (k, new internal vertex)
v. the edge (u, new internal vertex)
vi. the edge (v, new internal vertex)
4. Use recursion to compute {lij} matrix, then proceed with the computation of
the above formula.
RE: project coding python - buran - Dec-18-2020
what is your question?
RE: project coding python - LastStopDEVS - Dec-18-2020
Hello Marcel2807, I hope you are enjoying the holidays! Thanks for joining and welcome to the Python-Forum community. There are plenty of resources here and lots of useful information but you must first learn how to access it.
I would definitely suggest looking at the rules page first which I have linked below.
The Rules
This will teach you how to make a good post so that you can get all of your questions answered and continue working on your project.
I would also suggest using the search which is located on the top right of the page on the left of your Username and Avatar. The first of the two buttons (the one on the left) is the search option. When you click it a drop-down menu will come up. You can also use the Advanced Search which will let you put in additional parameters or tags to help find a specific post.
I hope this helps you or any other member on the website. Please always double-check your post before submitting!
LastStop|DEVS