Question: Let P = {alpha_1 .. alpha_n} be the x coordinates of a set of points, all on the horizontal line y = 0. Let Q

 Let P = {alpha_1 .. alpha_n} be the x coordinates of

Let P = {alpha_1 .. alpha_n} be the x coordinates of a set of points, all on the horizontal line y = 0. Let Q = {beta_1 .. beta_n) be the x coordinates of a set of points, all on the horizontal line y = 1. Each point is also associated with a label. This label is one of characters {A, C, T, G}. Suggest an algorithm, as efficient as possible that finds a set S of segments, satisfying all the following conditions: (a) Each segment of S connects a point of P to a point on Q. Point might me connected only if it matches the same label (for example. 'A' to 'A'). (b) No two segments of S cross each other (c) The length of each segment is at most some given threshold L (e.g. 17) (d) The cardinality of S is as large as possible

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!