A Convex Atomic-Norm Approach to Multiple Sequence Alignment and Motif Discovery

Ian En-Hsu Yen, Xin Lin, Jiong Zhang, Pradeep Ravikumar, Inderjit Dhillon
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2272-2280, 2016.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-yena16, title = {A Convex Atomic-Norm Approach to Multiple Sequence Alignment and Motif Discovery}, author = {Yen, Ian En-Hsu and Lin, Xin and Zhang, Jiong and Ravikumar, Pradeep and Dhillon, Inderjit}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2272--2280}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/yena16.pdf}, url = {https://proceedings.mlr.press/v48/yena16.html}, 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.} }
Endnote
%0 Conference Paper %T A Convex Atomic-Norm Approach to Multiple Sequence Alignment and Motif Discovery %A Ian En-Hsu Yen %A Xin Lin %A Jiong Zhang %A Pradeep Ravikumar %A Inderjit Dhillon %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-yena16 %I PMLR %P 2272--2280 %U https://proceedings.mlr.press/v48/yena16.html %V 48 %X 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.
RIS
TY - CPAPER TI - A Convex Atomic-Norm Approach to Multiple Sequence Alignment and Motif Discovery AU - Ian En-Hsu Yen AU - Xin Lin AU - Jiong Zhang AU - Pradeep Ravikumar AU - Inderjit Dhillon BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-yena16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2272 EP - 2280 L1 - http://proceedings.mlr.press/v48/yena16.pdf UR - https://proceedings.mlr.press/v48/yena16.html AB - 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. ER -
APA
Yen, I.E., Lin, X., Zhang, J., Ravikumar, P. & Dhillon, I.. (2016). A Convex Atomic-Norm Approach to Multiple Sequence Alignment and Motif Discovery. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2272-2280 Available from https://proceedings.mlr.press/v48/yena16.html.

Related Material