Efficient and Scalable Algorithms for Network Motifs Discovery Tese submetida a ̀ Faculdade de Ciências da Universidade do Porto para obtenção do grau de

First of all, I would like to thank my two advisors, Fernando Silva and Lúıs Lopes. They have always been there when I needed them, providing guidance, support and a lot of patience over the last years. Their collaboration was essential and we always had fruitful discussions on the emerging ideas on this subject. I would like to thank the financial support of FCT that was allowed me to dedicate the initial 4 years pursuing this research (PhD grant SFRH/BD/19753/2004). I would also like to thank CRACS/INESC-Porto L.A. for support on the fifth year, allowing me to further improve my work and finish my PhD. I would like to thank Paul Watson and particularly Marcus Kaiser for receiving me so well in Newcastle University for 3 months. This stay provided me with some of the initial motivation for entering the motif discovery and complex network analysis world. I would also like to thank all persons that helped in providing me the computational infrastructures that I used during my work. In particular Hugo Ribeiro, my brother and local computer science department network administrator, and Enrico Pontelli