Simple approximation algorithm for nonoverlapping local alignments

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simple approximation algorithm for nonoverlapping local alignments

Full text

Pdf (221 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California

Pages: 677 - 678

Year of Publication: 2002

ISBN:0-89871-513-X

Authors

Piotr Berman	Pennsylvania State University, University Park, PA
Bhaskar DasGupta	University of Illinois at Chicago, Chicago, IL
S. Muthukrishnan	AT&T Labs --- Research, Florham Park, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 2

Additional Information:

references cited by collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Vineet Bafna , Babu Narayanan , R. Ravi, Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles), Discrete Applied Mathematics, v.71 n.1-3, p.41-53, Dec. 5, 1996 [doi>10.1016/S0166-218X(96)00063-7]
	2	Piotr Berman, A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.214-219, July 05-07, 2000
	3	Piotr Berman , Bhaskar DasGupta, Improvements in throughout maximization for real-time scheduling, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.680-687, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335401]
	4	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	5	Magnús M. Halldórsson, Approximating discrete collections via local improvements, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.160-169, January 22-24, 1995, San Francisco, California, United States
	6	M. S. Waterman and M. Eggert, A new algorithm for best subsequence alignments with application to trna-rrna comparisons, J. Mol. Biol. 197, 1987, pp. 723-728.

CITED BY 2

	Hiroyuki Nagashima , Koichi Yamazaki, Hardness of approximation for non-overlapping local alignments, Discrete Applied Mathematics, v.137 n.3, p.293-309, 15 March 2004
	Miroslav Chlebík , Janka Chlebíková, Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia

Collaborative Colleagues:

Piotr Berman: colleagues

Bhaskar DasGupta: colleagues

S. Muthukrishnan: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player