Let P = {alpha_1 .. alpha_n} be the x coordinates of a set of points, all on the

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

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.