Name
Title | ||
|---|---|---|
Determining DNA Sequence Similarity Using Maximum Independent Set Algorithms for Interval Graphs |
Abstract | ||
|---|---|---|
Motivated by the problem of finding similarities in DNA and amino acid sequences, we study a particular class of two dimensional interval graphs and present an algorithm that finds a maximum weight increasing independent set for this class. Our class of interval graphs is a subclass of the graphs with interval number 2. The algorithm we present runs in O(n log n) time, where n is the number of nodes, and its implementation provides a practical solution to a common problem in genetic sequence comparison. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1007/3-540-55706-7_29 | SWAT |
Keywords | Field | DocType |
dna sequence similarity,maximum independent set algorithms,interval graphs,maximum independent set,dna sequence,genetics,independent set,interval graph,amino acid sequence | Discrete mathematics,Graph,Combinatorics,Complete sequence,Subclass,Interval graph,Algorithm,Independent set,DNA sequencing,Time complexity,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-55706-7 | 21 | 1.39 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deborah Joseph | 1 | 512 | 72.28 |
| Joao Meidanis | 2 | 85 | 11.44 |
| Prasoon Tiwari | 3 | 592 | 96.81 |