Abstract:

In the Nested Linear Graph model, the problem of finding the largest common secondary sequence of multiple ncRNA alignment is precisely the problem of finding the largest common nested linear sub-graph. By simplifying the model, it is proven that this problem is NP-Complete in the condition of pseudo-flat nested linear graph, and an approximate algorithm for the largest level nested linear sub-graph is given.

Key words: linear graph; nested; integral sub-graph; subsequence; NP-Complete