Ask Question, Ask an Expert

+61-413 786 465

info@mywordsolution.com

Ask Python Expert

Assignment: Introduction to Computer Science for Life Scientists

Exercise 1 (Dynamic Programming)

Searching for the longest common subsequence (LCS) of biosequences is one of the most important tasks in Bioinformatics. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example given a sequence S =\AGGTACCCGATC", all \AGT", \TAGAT", \GGG", and ... are subsequences of S.. In Bioinformatics the length of the longest commen subsequence between two biosequences is a good measure for the similarity of the two sequences.

a) Write a recursive function to and the LCS of two input string of size n and m. (3P)

b) For two sequences of size n, what is the running time complexity of your function in part a), where all possible subsequences are computed for both sequences? Brie y explain your answer. (2P)

c) This time use dynamic programming to nd the LCS of two input string of size n and m. (5P)

d) Write a python function that uses your idea in part c) to nd the LCS of two input strings S1 and S2. Test your function with the following sequences: (3P)

S1=\AGGTACCCGATC", S2=\GTAAGAGTACCGATTGATC"
S1=\AGATTCCCCACCTTAGA", S2=\AGGAATCCCCAACCTGA"

e) Briefly explain what is the running time complexity of LCS function in part d)? (2P)

Exercise 2 (Sorting)

a) Suggest an algorithm with O(n) average running time complexity to nd the ith smallest value in set S of size n. For example for S = f5; 3; 1; 7; 2; 3; 1g the third smallest element is 2. You are not allowed to use counting or radix sort. Hint: Think how you could make use of the idea of quick sort for searching. (5P)

b) Suggest an algorithm with O(nk) running time complexity to sort a list of n strings, where the strings may have di erent lengths with k being the length of the longest string. For example for [\b",\cda",\db",\da",\ab",\a"], the sorted list must be [\a",\ab",\b",\cda",\da",\db"]. (5P).

Python, Programming

  • Category:- Python
  • Reference No.:- M92556057
  • Price:- $30

Priced at Now at $30, Verified Solution

Have any Question?


Related Questions in Python

Show times in tmus and seconds1 an associate grasps an oven

Show times in TMUs and seconds. 1. An associate grasps an oven door within reach and pulls it open 18 inches with the left hand (he does not relinquish control of the door). With a pan in the right hand, he carefully pos ...

Simple python traffic lightswrite a program that simulates

Simple Python (Traffic lights) Write a program that simulates a traffic light. The program lets the user select one of three lights: red, yellow, or green. When a radio button is selected, the light is turned on, and onl ...

Learning outcomes lo3 - research develop and document a

Learning Outcomes LO3 - Research, develop, and document a basic security policy, and analyse, record, and resolve all security incidents LO4 - Identify and assess the threats to, and vulnerabilities of networks Assessmen ...

Question research pythons dictionary data type dictdiscuss

Question : Research Python's dictionary data type (dict). Discuss its interface and usage. Include examples. Discuss practical applications of dictionaries.

A software company sells a package that retails for 99

A software company sells a package that retails for $99. Quantity discounts are given according to the following table: Quantity Discount 10 - 19 20% 20 - 49 30% 50 - 99 40% 100 or more 50% Write a program using python t ...

Question a software company sells a package that retails

Question : A software company sells a package that retails for $99. Quantity discounts are given according to the following table: Quantity Discount 10 - 19 20% 20 - 49 30% 50 - 99 40% 100 or more 50% Write a program usi ...

The second task in this assignment is to create a python

The second task in this assignment is to create a Python program called pancakes.py that will determine the final order of a stack of pancakes after a series of flips.(PYTHON 3) Problem Task In this problem, your input w ...

Foundations of programming assignment - feduni bankingthis

Foundations of Programming Assignment - FedUni Banking This assignment will test your skills in designing and programming applications to specification. Assignment Overview - You are tasked with creating an application t ...

Questionwhat is a python development frameworkgive 3

Question What is a python development framework? Give 3 examples python development framework used today. and explain which development framework is used in which industry.

Environment setupthe first mini project will be based on

Environment Setup The first mini project will be based on Ladder Logic programming. We will be using Schneider Electric's IDE called SoMachine Basic to do the programming. The latest ver- sion of SoMachine Basic for Wind ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As