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 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
Get step-by-step solutions from verified subject matter experts
