On two open problems of 2-interval patterns

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

6 Scopus Citations
Scopus Metrics
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)2410-2423
Journal / PublicationTheoretical Computer Science
Volume410
Issue number24-25
Publication statusPublished - 28 May 2009
Externally publishedYes

Link(s)

DOI

DOI
Check@CityULib
Link to Scopus https://www.scopus.com/record/display.uri?eid=2-s2.0-67349188490&origin=recordpage
Permanent Link https://scholars.cityu.edu.hk/en/publications/publication(1a11a5cd-eddc-4778-8679-f12851de1bc2).html

Abstract

The 2-interval pattern problem, introduced in [Stéphane Vialette, On the computational complexity of 2-interval pattern matching problems Theoret. Comput. Sci. 312 (2-3) (2004) 223-249], models general problems with biological structures such as protein contact maps and macroscopic describers of secondary structures of ribonucleic acids. Given a set of 2-intervals D and a model R, the problem is to find a maximum cardinality subset D′ of D such that any two 2-intervals in D′ satisfy R, where R is a subset of relations on disjoint 2-intervals: precedence (11The second part of this paper appeared in WABI'2006. © 2009 Elsevier B.V. All rights reserved.

Research Area(s)

  • 2-interval pattern, Bioinformatics, Contact map, NP-hard

Fingerprint

Publication fingerprints text

100
Cardinality Mathematics
100
Matching Problem Mathematics
100
Open Problem Mathematics
100
Secondary Structure Mathematics
Full Fingerprint ›

Citation Format(s)

[ RIS ] [ BibTeX ]
On two open problems of 2-interval patterns. / Li, Shuai Cheng; Li, Ming.
In: Theoretical Computer Science, Vol. 410, No. 24-25, 28.05.2009, p. 2410-2423.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review