Constraint-based analysis of genome-scale metabolic networks has become increasingly important for describing and predicting the cellular behavior of living organisms. The steady-state constraints provide a reliable framework without the need for additional kinetic details of the system. As the number of metabolic network reconstructions and their level of detail continually increases, many computational tools for their analysis become unpractical to use. This invites for more efficient algorithms and tools for the analysis of metabolic networks. We have a two-fold aim with this work: first, to design new algorithms that improve the efficiency of some of the existing methods, secondly to create additional tools that fill in gaps in our toolbox for metabolic network analysis. These methods will provide additional insight into the structure of metabolic networks and ultimately broaden our understanding of cellular systems. In the first part of the thesis we focus on improving flux coupling analysis (FCA). We prove that solving certain linear programs to feasibilty is sufficient to correctly deduce most coupling information. The FFCA algorithm improves the efficiency of existing algorithms in the literature and is further developed by proving that all fully coupled reactions can be computed algebraically. Utilizing the transitive nature of couplings and reusing existing LP solutions we can dramatically decrease running-time. Using these improvements we design the F2C2 algorithm. We extend the concepts of FCA to the constrained flux space, where any number of additional linear constraints can be imposed on the reactions. Constrained flux coupling analysis (CFCA) is proven to reveal coupling information that is only visible under special environmental conditions. We study the relationship between the FCA and CFCA relations and present an efficient algorithm to compute the latter. In our next effort we study whether relations similar to FCA could also be applied for metabolites. We introduce the concept of metabolic activity coupling (MAC), which finds implicative relations between the momentary production and consumption of different metabolites. Elementary flux modes (EM) are a canonical representation of the steady-state flux space. Our novel method for finding EMs containing several predefined reactions can be used to identify pathways that synthesize a desired target from one or more source metabolites. While the problem solved belongs to the class of NP-hard problems, we show that for current-generation networks the method is applicable in practice. In the last part of the thesis, we show that the study of isolated subnetworks may result in undesired artifacts, and as an alternative solution, we present a method that projects the flux space onto lower dimension, while preserving key features of the network. We show that in certain cases our method can be applied where an exhaustive EM enumeration would otherwise fail.