title: A cost-aggregating integer linear program for motif finding.
abstract: In the motif finding problem one seeks a set of mutually similar substrings within a collection of biological sequences. This is an important and widely-studied problem, as such shared motifs in DNA often correspond to regulatory elements. We study a combinatorial framework where the goal is to find substrings of a given length such that the sum of their pairwise distances is minimized. We describe a novel integer linear program for the problem, which uses the fact that distances between substrings come from a limited set of possibilities allowing for aggregate consideration of sequence position pairs with the same distances. We show how to tighten its linear programming relaxation by adding an exponential set of constraints and give an efficient separation algorithm that can find violated constraints, thereby showing that the tightened linear program can still be solved in polynomial time. We apply our approach to find optimal solutions for the motif finding problem and show that it is effective in practice in uncovering known transcription factor binding sites.
authors.affiliation: Center for Bioinformatics & Computational Biology and Department of Computer Science, University of Maryland, College Park, MD.
authors.forename: Carl
authors.initials: C
authors.lastname: Kingsford
authors.forename: Elena
authors.initials: E
authors.lastname: Zaslavsky
authors.forename: Mona
authors.initials: M
authors.lastname: Singh
references.citation: Bioinformatics. 1999 Jul-Aug;15(7-8):563-77
references.pmid: 10487864
references.citation: Science. 2002 Oct 25;298(5594):799-804
references.pmid: 12399584
references.citation: Bioinformatics. 2004 Dec 12;20(18):3516-25
references.pmid: 15297295
references.citation: J Mol Biol. 1998 Nov 27;284(2):241-54
references.pmid: 9813115
references.citation: Nature. 2003 May 15;423(6937):241-54
references.pmid: 12748633
references.citation: Algorithms Mol Biol. 2006 Aug 17;1:13
references.pmid: 16916460
references.citation: Bioinformatics. 2005 Apr 1;21(7):1028-36
references.pmid: 15546935
references.citation: J Comput Biol. 2000;7(3-4):345-62
references.pmid: 11108467
references.citation: Proteins. 1991;9(3):180-90
references.pmid: 2006136
references.citation: Nat Genet. 1999 Jul;22(3):281-5
references.pmid: 10391217
references.citation: Proc Int Conf Intell Syst Mol Biol. 2000;8:269-78
references.pmid: 10977088
references.citation: Nucleic Acids Res. 2003 Jul 1;31(13):3580-5
references.pmid: 12824370
references.citation: J Comput Biol. 1994 Winter;1(4):337-48
references.pmid: 8790475
references.citation: Nat Biotechnol. 2005 Jan;23(1):137-44
references.pmid: 15637633
references.citation: Science. 1993 Oct 8;262(5131):208-14
references.pmid: 8211139
references.citation: Genome Res. 2000 Jun;10(6):744-57
references.pmid: 10854408