Let P = {alpha_1 .. alpha_n} be the x coordinates of a set of points, all on the
ID: 3866158 • Letter: L
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 = {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.Explanation / Answer
Algorithm to find the set S of segment:
1. Let assume n given lines of segment S. There must be double end points to represent n lines.
Sort all points according to alpha coordinates, during sorting keep one flag to check this point is left point of
its line or right point.
2. If the current point is a right point, here we need to check intersect with each other.
Same as we check current point is a left point same way we will check intersect with each other.
3. (A, C, T, G) of P and Q have different orientations, that will make sure there is no two segment of S cross each other
4. Create a copy of every Iteratation of set of S in the current power-set that will give maximum cardinality
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.