title: A Convex Atomic-Norm Approach to Multiple Sequence Alignment and Motif Discovery.
abstract: Multiple Sequence Alignment and Motif Discovery, known as NP-hard problems, are two fundamental tasks in Bioinformatics. Existing approaches to these two problems are based on either local search methods such as Expectation Maximization (EM), Gibbs Sampling or greedy heuristic methods. In this work, we develop a convex relaxation approach to both problems based on the recent concept of atomic norm and develop a new algorithm, termed Greedy Direction Method of Multiplier, for solving the convex relaxation with two convex atomic constraints. Experiments show that our convex relaxation approach produces solutions of higher quality than those standard tools widely-used in Bioinformatics community on the Multiple Sequence Alignment and Motif Discovery problems.
authors: Department of Computer Science, University of Texas at Austin, TX 78712, USA.
authors: Ian E H
authors: IE
authors: Yen
authors: Department of Computer Science, University of Texas at Austin, TX 78712, USA.
authors: Xin
authors: X
authors: Lin
authors: Institute for Computational Engineering and Sciences, University of Texas at Austin, TX 78712, USA.
authors: Jiong
authors: J
authors: Zhang
authors: Department of Computer Science, University of Texas at Austin, TX 78712, USA; Institute for Computational Engineering and Sciences, University of Texas at Austin, TX 78712, USA.
authors: Pradeep
authors: P
authors: Ravikumar
authors: Department of Computer Science, University of Texas at Austin, TX 78712, USA; Institute for Computational Engineering and Sciences, University of Texas at Austin, TX 78712, USA.
authors: Inderjit S
authors: IS
authors: Dhillon